Gabriela

4654

Let us consider the general case when n ¼ 2
m
. Note that the number of recursion levels is
m. Also, note that to merge a sorted list of size s with a sorted list of size t, the maximumnumber of comparisons is s + t 1.
Consider the function mergeList, which merges two sorted lists into a sorted list. Note
that this is where the actual work, comparisons and assignments, is done.The initial call
to the function recMergeSort, at level 0, produces two sublists, each of size n / 2. To
merge these two lists, after they are sorted, the maximum number of comparisons is n / 2 +
n /2 – 1 ¼ n – 1 ¼ O(n). At level 1, we merge two sets of sorted lists, where each sublist is
of size n / 4. To merge two sorted sublists, each of size n / 4, we need at most n / 4 + n / 4 –
1 ¼ n / 2– 1 comparisons. Thus, at level 1 of the recursion, the number of comparisons is
2(n / 2 – 1) ¼ n – 2 ¼ O(n). In general, at level k of the recursion, there are a total of 2
k
calls
8
4 4
2 2 21
2
Recursion Level: 0
Number of calls to recMergeSort: 1
Each call: recMergeSort 8 elements
Recursion Level: 1
Number of calls to recMergeSort: 2
Each call: recMergeSort 4 elementsRecursion Level: 2
Number of calls to recMergeSort: 4
Each call: recMergeSort 2 elements
Recursion Level: 3
Number of calls to recMergeSort: 8
Each call: recMergeSort 1 elements
1 1 1 1 1 1 1
F IG UR E 1 0 - 4 0 Levels of recursion levels to recMergeSort for a list of length 8
566 | Chapter 10: Sorting Algorithmsto the function mergeList. Each of these calls merge two sublists, each of sizen / 2
k + 1
,
which requires a maximum of n / 2
k
1 comparisons. Thus, at level k of the recursion, the
maximum number of comparisons is 2
k
(n / 2
k
1) ¼ n 2
k
¼ O(n). It now followsthat
the maximum number of comparisons at each level of the recursion is O(n). Because the
number of levels of the recursion is m, the maximum number of comparisons made by
mergesort is O(nm)....