This is what we call the ???top-level??? of recursion,
level 0.
20 ALGORITHMS [CHAP. 2
2 merge_sort calls merge_sort again, passing a list of the first two numbers in NUMS. This will
sort the front half of the list. This is level 1 of recursion.
3 Now merge_sort calls merge_sort again, passing only the first number in NUMS. This is level 2.
4 Now merge_sort simply returns; it??™s down to one element in the list, merge_sort returns to level 1.
5 Now merge_sort calls merge_sort again, passing only the second of the first two numbers in
NUMS. This is level 2.
6 Again, merge_sort simply returns; it??™s down to one element in the list, merge_sort returns to level 1.
7 At level 1 of recursion, merge_sort now has result_A and result_B. merge_sort calls
merge to put those two numbers in order, and then it returns the sorted pair of numbers back to level 0.
The first half of the list is sorted.
8 From level 0, merge_sort calls merge_sort again, passing a list of the last two numbers in NUMS.
This will sort the back half of NUMS. It??™s back to level 1 of recursion.
9 merge_sort calls merge_sort again, passing only the first of the last two numbers of NUMS. This is
level 2 of recursion again.
10 Since the list contains only one number, merge_sort simply returns back to level 1.
Pages:
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64