11 merge_sort calls merge_sort again, passing only the last of the numbers of NUMS. This is level 2
of recursion again.
12 Since the list contains only one number, merge_sort simply returns back to level 1.
13 At level 1 of recursion, merge_sort now has result_A and result_B. merge_sort calls
merge to put the two lists in order, and then it returns the sorted set of two numbers back to level 0.
14 At level 0 of recursion, merge_sort now has result_A and result_B. merge_sort calls merge
to put the two lists of numbers in order, and then it returns the entire set of four numbers in sorted order.
Aside from being an interesting exercise in recursion, the merge_sort provides attractive performance. The
merge sort has a theta of n(lg n), which for large problems is much better than the theta of n2 for the insertion sort.
The recursion in merge_sort divides the problem into many subproblems by repeatedly halving the size
of the list to be sorted. The number of times the list must be divided by two in order to create lists of length one
is equal to the logarithm to the base 2 of the number of elements in the list.
In the case of our 4-element example, the logarithm to the base 2 of 4 is 2, because 22 = 4.
Pages:
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65