The merge routine continues in this manner until all the cards have been moved
into the sorted merged pile.
Here is pseudocode for the merge routine. It expects to work on two previously sorted lists of numbers, and
it merges the two lists into one sorted list, which it returns. The variable index keeps track of where it is working
in sorted_list.
The routine compares the first (top) numbers in the two original lists, and puts the smaller of the two into
sorted_list. Then it discards the number from the original list, which means that the number that used to
be the second one in the original list becomes the first number in that list. Again the routine compares the first
numbers in the two lists, and again it moves the smaller to sorted_list.
The routine continues this way until one of the original lists becomes empty. At that point, it adds the remaining
numbers (which were in sorted order originally, remember) to sorted_list, and returns sorted_list.
merge(list_A, list_B)
// index keeps track of where we are in the
// sorted list
index <-- 1
// Repeat as long as there are numbers in both
// original lists.
while list_A is not empty AND list_B is not empty
// Compare the 1st elements of the 2 lists.
Pages:
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61