Merging and Mergesort L: 12 18 23 29 R: 14 17 22 31 33
i j L[i] > R[j];
A[k] = R[j];
Merging: Merging two (or more) lists means combining the lists, A: 12 14 17 18 ++j; ++k;
which must already be sorted, into a single sorted list. k
Merging is easier than sorting. There is a very efficient algorithm
for merging, illustrated below. Arrays L and R are merged into A. L: 12 18 23 29 R: 14 17 22 31 33
i j L[i] ≤ R[j];
L: 12 18 23 29 R: 14 17 22 31 33 A[k] = L[i];
A: 12 14 17 18 22 ++i; ++k;
i j L[i] ≤ R[j];
k
A[k] = L[i];
A: ++i; ++k;
k L: 12 18 23 29 R: 14 17 22 31 33
i j L[i] ≤ R[j];
A[k] = L[i];
L: 12 18 23 29 R: 14 17 22 31 33
A: 12 14 17 18 22 23 ++i; ++k;
i j L[i] > R[j];
k
A[k] = R[j];
A: 12 ++j; ++k;
k L: 12 18 23 29 R: 14 17 22 31 33
i j End of L.
Copy rest
L: 12 18 23 29 R: 14 17 22 31 33
A: 12 14 17 18 22 23 29 of R to A.
i j L[i] > R[j];
k
A[k] = R[j];
A: 12 14 ++j; ++k;
k L: 12 18 23 29 R: 14 17 22 31 33
i j All done!
L: 12 18 23 29 R: 14 17 22 31 33 A: 12 14 17 18 22 23 29 31 33
i j L[i] ≤ R[j]; k
A[k] = L[i];
A: 12 14 17 ++i; ++k; Unfortunately, this algorithm does not work in place. (L and R cannot
k occupy the same memory as A.)
Algorithm for Merging: In our merging algorithm, we assume that
the lists being merged occupy contiguous ranges within an array A, and If it is feasible to place an extra element, with value ∞, at the end of L
the merged list is stored back to the union of these ranges. That is, we and R, we can shorten the algorithm a bit.
merge A[p .. q] and A[q+1 .. r] to A[p .. r]. Here ∞ need merely be greater than the largest possible element of L
or R.
Input: An array A of element type T, where T has a strict weak
ordering (denoted by <), and integers p, q, and r with p ≤ q ≤ r,
such that A[p .. q] and A[q+1 .. r] are sorted. Algorithm (alternate version):
Output: The array A, with A[p .. r] sorted and the remaining elements void merge2( T[] A, Integer p, Integer q, Integer r)
unchanged. L = temp array of size 1..q–p+2;
L[1..q–p+1] = A[p..q]; L[q–p+2] = ∞;
Algorithm: R = temp array of size 1..r–q+1;
R[1..r–q] = A[q+1..r]; R[r–q+1] = ∞;
void merge( T[] A, Integer p, Integer q, Integer r)
L = temp array of size 1..q–p+1; i = 1; j = 1; // i, j, k = current positions in L, R, A.
L[1..q–p+1] = A[p..q]; for ( k = p, p+1, ..., r–1, r ) // Merge from L and R to A.
R = temp array of size 1..r–q; if ( L[i] < R[j] )
R[1..r–q] = A[q+1..r]; A[k] = L[i];
i = 1; j = 1; k = p; // i, j, k = current positions in L, R, A. ++i;
else
while ( i ≤ q–p+1 and j ≤ r–q ) // Merge from L and R to A until
A[k] = R[j];
if ( L[i] < R[j] ) // one of L or R is exhausted.
++j;
A[k] = L[i];
++i; ++k;
else
A[k] = R[j];
++j; ++k; Analysis of merging:
while ( i ≤ q–p+1 ) // Copy remainder of L to A.
A[k] = L[i]; We consider two basic operations:
++i; ++k; i) Comparisons of array elements. C(n) = no of comparisons.
while ( j ≤ r–q ) // Copy remainder of R to A ii) Moves (copying) of array elements. M(n) = no of moves.
A[k] = R[j]; Here n = r–p+1 (the input size).
++j; ++k;
merge( ) performs n–1 comparisons in the worst case: Mergesort: Mergesort is a divide-and-conquer algorithm for sorting.
Cmax(n) = n–1 .
To sort an array A[p .. r] (a problem with input size n = r–p+1) using
mergesort, we
merge( ) performs nearly n–1 comparisons in the expected case, if the
two lists being merged have comparable size, and elements are i) [Divide] Divide into two subproblems by setting q = (p+r)/2
randomly distributed between the lists: and defining
Cave(n) ≈ n–1 under appropriate assumptions. Subproblem 1: Sort A[p .. q] (input size = n/2 ).
Subproblem 2: Sort A[q+1 .. r] (input size = n/2 ).
merge( ) always performs 2n moves:
ii) [Solve subproblems] Solve each subproblem by invoking
Mmax(n) = Mave(n) = 2n . mergesort recursively, unless the subproblem has size 1.
iii) [Combine] Merge the (now sorted) subarrays A[p .. q] and
merge2( ) performs n comparisons and 2n (or 2n+2) moves in all cases.
A[q+1 .. r] into a sorted array A[p .. r]. This may be done by
invoking merge( A, p, q, r).
Both merging algorithms run in linear time: T(n) = Θ(n) in all cases.
However, if n = 1, we don’t divide into subproblems. In fact, there is
nothing to do; the array is already sorted.
Other nice features of merging:
i) merge() accesses all arrays in forward sequential order.
a) This means that it can be adapted easily to merge singly or
doubly linked lists.
ii) Our merging algorithms are stable, in the following sense:
If i < j and A[i] ∼ A[j], and if merge() moves A[i] to position i'
and A[j] to position j', then i' < j'. In other words, the relative
order of equivalent elements is preserved.
A[i] ∼ A[j] might mean that structures A[i] and A[j] agree on
their key field (used to sort), but possibly not on other fields.
We have derived a recurrence equation for Cmax(n).
Algorithm for Mergesort:
For any specific n, we can compute Cmax(n) explicitly.
Input: An array A of element type T, where T has a strict weak
ordering (denoted by <), and integers p and r with p ≤ r.
n Cmax(n)
Output: The array A, with A[p .. r] sorted and the remaining elements 1 0
unchanged. 2 2–1+C(1)+C(1) = 1
3 3–1+C(2)+C(1) = 3
Algorithm: 4 4–1+C(2)+C(2) = 5
void mergesort( T[] A, Integer p, Integer r) 5 5–1+C(3)+C(2) = 8
if ( p < r ) 6 6–1+C(3)+C(3) = 11
q = (p+r)/2; 7 7–1+C(4)+C(3) = 14
8 8–1+C(4)+C(4) = 17
mergesort( A, p, q);
9 9–1+C(5)+C(4) = 21
mergesort( A, q+1, r);
10 10–1+C(5)+C(5) = 25
merge( A, p, q, r); 11 11–1+C(6)+C(5) = 29
12 12–1+C(6)+C(6) = 33
13 13–1+C(7)+C(6) = 37
Analysis of Mergesort: 14 14–1+C(7)+C(7) = 41
15 15–1+C(8)+C(7) = 45
We count the number C(n) of comparisons of elements of A. Consider 16 16–1+C(8)+C(8) = 49
the worst case.
If n = 1, no comparisons are required. This isn’t too useful! It would be much nicer to obtain Cmax(n) as a
simple function.
Otherwise:
Step (i) is trivial and uses no comparisons. Unfortunately, we can’t do this because of the floors and ceilings in
the recurrence Cmax(n) = n – 1 + Cmax( n/2 ) + Cmax( n/2 ).
Step (ii) requires Cmax( n/2 ) + Cmax( n/2 ) comparisons, in the
worse case Even if n is even, at on some recursive call we are likely to have a
Step (iii) requires n – 1 comparisons, in the worst case. list of odd size.
But if n is a power of 2, we can split the list exactly in half on every
Cmax(1) = 0,
recursive call to mergesort(), and the recurrence simplifies to
Cmax(n) = n – 1 + Cmax( n/2 ) + Cmax( n/2 ), if n > 1.
Cmax(n) = n – 1 + 2Cmax( n/2).
We start by assuming that n is a power of 2, say n = 2k. Then k = lg(n).
Cmax(n) = n – 1 + 2Cmax(n/2)
= n – 1 + 2( n/2 – 1 + 2Cmax(n/22) )
= 2n – (1 + 2) + 22Cmax(n/22)
= 2n – (1+2) + 22( n/22 – 1 + 2Cmax(n/23) )
= 3n – (1 +2+22) + 23 Cmax(n/23)
.
.
.
= kn – (1 + 2+22+...+2k–1) + 2k Cmax(n/2k)
= n lg(n) – (n–1) + 0 (since k = lg(n) and n/2k = 1)
= n lg(n) – n + 1
So Cmax(n) = n lg(n) – n + 1 exactly, when n is a power of 2.
What if n is not a power of 2? Then, at some step, we cannot divide the
list exactly in half. But except for very small n, we divide it into two
lists of nearly equal size (ratio of sizes very close to 1).
We might expect the ratio of Cmax(n) to n lg(n) – n + 1 to be only
slightly greater than 1.
The handout Recurrences: Approximating n/2 and n/2 by n/2
shows that this is correct, at least for n < 106.
Note, for example, that for 103 ≤ n < 104,
n lg(n) – n + 1 ≤ Cmax(n) < 1.0091(n lg(n) – n + 1)
and that for larger n the approximation is even better.
So we will use Cmax(n) ≈ n lg(n) – n + 1 as our solution, in general.
Cave(n) is only slightly less than Cmax(n).