In fact, merge_sort divides the list of numbers until each sublist consists of a single number, which can be
considered a sorted list of length 1. Then the merge_sort uses the merge procedure to join the sorted sublists.
The technique used by merge_sort to divide the problem into subproblems is called recursion. The
merge_sort repeatedly calls itself until the recursion ???bottoms out??? with lists whose lengths are one. Then
the recursion ???returns,??? reassembling the numbers in sorted order as it does. Here is pseudocode for the merge
sort. It takes the list of numbers to be sorted, and it returns a sorted list of those numbers.
merge_sort(num_list)
length <-- length of num_list
// if there is more than 1 number in the list,
if length > 1
// divide the list into two lists half as long
shorter_list_A <-- first half of num_list
shorter_list_B <-- second half of num_list
// Perform a merge sort on each shorter list
result_A <-- merge_sort(shorter_list_A)
result_B <-- merge_sort(shorter_list_B)
// Merge the results of the two sorted sublists
sorted_list <-- merge(result_A, result_B)
// Return the sorted list
return sorted_list
else
// If there??™s only 1 number in the list,
// just return it
return num_list
end
Let??™s follow the execution of merge_sort when one calls it with this list of numbers:
NUMS = { 1, 6, 4, 2 }
1 First, we call merge_sort passing the list NUMS.
Pages:
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63