// Move the smaller to the sorted list.
// "<" means "smaller than."
if list_A[1] < list_B[1]
sorted_list[index] <-- list_A[1]
discard list_A[1]
else
sorted_list[index] <-- list_B[1]
discard list_B[1]
index <-- index + 1
// If numbers remain only in list_A, move those
// to the sorted list
while list_A is not empty
sorted_list[index] <-- list_A[1]
discard list_A[1]
index <-- index + 1
CHAP. 2] ALGORITHMS 19
// If numbers remain only in list_B, move those
// to the sorted list
while list_B is not empty
sorted_list[index] <-- list_B[1]
discard list_B[1]
index <-- index + 1
// Return the sorted list
return sorted_list
The performance of merge is related to the lengths of the lists on which it operates, the total number of
items being merged. The real work of the routine is in moving the appropriate elements of the original lists into
the sorted list. Since the total number of such moves is equal to the sum of the numbers in the two lists, merge
has a theta of nA + nB, or ??(nA + nB), where nA + nB is equal to the sum of the numbers in the two lists.
The merge_sort will use the merge routine, but first the merge_sort will divide the problem up into
smaller and smaller sorting tasks. Then merge_sort will reassemble the small sorted lists into one fully sorted list.
Pages:
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62