A sorting algorithm based on divide and conquer. Its worst-case running time has
a lower order of growth than insertion sort.
Because we are dealing with subproblems, we state each subproblem as sorting
a subarray A[p . . r ]. Initially, p = 1 and r = n, but these values change as we
recurse through subproblems.
To sort A[p . . r ]:
Divide by splitting into two subarrays A[p . . q] and A[q + 1 . . r ], where q is the
halfway point of A[p . . r ].
Conquer by recursively sorting the two subarrays A[p . . q] and A[q + 1 . . r ].
Combine by merging the two sorted subarrays A[p . . q] and A[q + 1 . . r ] to produce
a single sorted subarray A[p . . r ]. To accomplish this step, we’ll deÞne a
procedure MERGE(A, p, q, r ).
The recursion bottoms out when the subarray has just 1 element, so that it’s trivially
sorted.
MERGE-SORT(A, p, r )
if p < r Check for base case
then q ← (p + r)/2
Divide
MERGE-SORT(A, p, q) Conquer
MERGE-SORT(A, q + 1, r ) Conquer
MERGE(A, p, q, r ) Combine
Initial call: MERGE-SORT(A, 1, n)
[It is astounding how often students forget how easy it is to compute the halfway
point of p and r as their average (p + r)/2. We of course have to take the ßoor
to ensure that we get an integer index q. But it is common to see students perform
calculations like p +(r − p)/2, or even more elaborate expressions, forgetting the
easy way to compute an average.]
Example: Bottom-up view for n = 8: [Heavy lines demarcate subarrays used in
subproblems.]
[Examples when n is a power of 2 are most straightforward, but students might
also want an example when n is not a power of 2.]
Bottom-up view for n = 11:
Merging
What remains is the MERGE procedure.
Input: Array A and indices p, q, r such that
• p ≤ q < r .
• Subarray A[p . . q] is sorted and subarray A[q + 1 . . r ] is sorted. By the
restrictions on p, q, r , neither subarray is empty.
Output: The two subarrays are merged into a single sorted subarray in A[p . . r ].
We implement it so that it takes (n) time, where n = r − p + 1 = the number of
elements being merged.
What is n? Until now, n has stood for the size of the original problem. But now
we’re using it as the size of a subproblem. We will use this technique when we
analyze recursive algorithms. Although we may denote the original problem size
by n, in general n will be the size of a given subproblem.
Idea behind linear-time merging: Think of two piles of cards.
• Each pile is sorted and placed face-up on a table with the smallest cards on top.
• We will merge these into a single sorted pile, face-down on the table.
• A basic step:
• Choose the smaller of the two top cards.
• Remove it from its pile, thereby exposing a new top card.
• Place the chosen card face-down onto the output pile.
• Repeatedly perform basic steps until one input pile is empty.
• Once one input pile empties, just take the remaining input pile and place it
face-down onto the output pile.
• Each basic step should take constant time, since we check just the two top cards.
• There are ≤ n basic steps, since each basic step removes one card from the
input piles, and we started with n cards in the input piles.
• Therefore, this procedure should take (n) time.
We don’t actually need to check whether a pile is empty before each basic step.
• Put on the bottom of each input pile a special sentinel card.
• It contains a special value that we use to simplify the code.
• We use ∞, since that’s guaranteed to “lose” to any other value.
• The only way that ∞ cannot lose is when both piles have ∞ exposed as their
top cards.
• But when that happens, all the nonsentinel cards have already been placed into
the output pile.
• We know in advance that there are exactly r − p + 1 nonsentinel cards ⇒stop
once we have performed r − p + 1 basic steps. Never a need to check for
sentinels, since they’ll always lose.
• Rather than even counting basic steps, just Þll up the output array from index p
up through and including index r .
Pseudocode:
MERGE(A, p, q, r )
n1 ← q − p + 1
n2 ←r − q
create arrays L[1 . . n1 + 1] and R[1 . . n2 + 1]
for i ← 1 to n1
do L[i ] ← A[p + i − 1]
for j ← 1 to n2
do R[ j ] ← A[q + j ]
L[n1 + 1]←∞
R[n2 + 1]←∞
i ← 1
j ← 1
for k ← p to r
do if L[i ] ≤ R[ j ]
then A[k] ← L[i ]
i ←i + 1
else A[k] ← R[ j ]
j ← j + 1
[The book uses a loop invariant to establish that MERGE works correctly. In a
lecture situation, it is probably better to use an example to show that the procedure
works correctly.]
Example: A call of MERGE(9, 12, 16)
[Read this Þgure row by row. The Þrst part shows the arrays at the start of the
“for k ← p to r” loop, where A[p . . q] is copied into L[1 . . n1] and A[q+1 . . r ] is
copied into R[1 . . n2]. Succeeding parts show the situation at the start of successive
iterations. Entries in A with slashes have had their values copied to either L or R
and have not had a value copied back in yet. Entries in L and R with slashes have
been copied back into A. The last part shows that the subarrays are merged back
into A[p . . r ], which is now sorted, and that only the sentinels (∞) are exposed in
the arrays L and R.]
Running time: The Þrst two for loops take O(n1 +n2) = O(n) time. The last for
loop makes n iterations, each taking constant time, for O(n) time.
Total time: O(n).
a lower order of growth than insertion sort.
Because we are dealing with subproblems, we state each subproblem as sorting
a subarray A[p . . r ]. Initially, p = 1 and r = n, but these values change as we
recurse through subproblems.
To sort A[p . . r ]:
Divide by splitting into two subarrays A[p . . q] and A[q + 1 . . r ], where q is the
halfway point of A[p . . r ].
Conquer by recursively sorting the two subarrays A[p . . q] and A[q + 1 . . r ].
Combine by merging the two sorted subarrays A[p . . q] and A[q + 1 . . r ] to produce
a single sorted subarray A[p . . r ]. To accomplish this step, we’ll deÞne a
procedure MERGE(A, p, q, r ).
The recursion bottoms out when the subarray has just 1 element, so that it’s trivially
sorted.
MERGE-SORT(A, p, r )
if p < r Check for base case
then q ← (p + r)/2
Divide
MERGE-SORT(A, p, q) Conquer
MERGE-SORT(A, q + 1, r ) Conquer
MERGE(A, p, q, r ) Combine
Initial call: MERGE-SORT(A, 1, n)
[It is astounding how often students forget how easy it is to compute the halfway
point of p and r as their average (p + r)/2. We of course have to take the ßoor
to ensure that we get an integer index q. But it is common to see students perform
calculations like p +(r − p)/2, or even more elaborate expressions, forgetting the
easy way to compute an average.]
Example: Bottom-up view for n = 8: [Heavy lines demarcate subarrays used in
subproblems.]
[Examples when n is a power of 2 are most straightforward, but students might
also want an example when n is not a power of 2.]
Bottom-up view for n = 11:
Merging
What remains is the MERGE procedure.
Input: Array A and indices p, q, r such that
• p ≤ q < r .
• Subarray A[p . . q] is sorted and subarray A[q + 1 . . r ] is sorted. By the
restrictions on p, q, r , neither subarray is empty.
Output: The two subarrays are merged into a single sorted subarray in A[p . . r ].
We implement it so that it takes (n) time, where n = r − p + 1 = the number of
elements being merged.
What is n? Until now, n has stood for the size of the original problem. But now
we’re using it as the size of a subproblem. We will use this technique when we
analyze recursive algorithms. Although we may denote the original problem size
by n, in general n will be the size of a given subproblem.
Idea behind linear-time merging: Think of two piles of cards.
• Each pile is sorted and placed face-up on a table with the smallest cards on top.
• We will merge these into a single sorted pile, face-down on the table.
• A basic step:
• Choose the smaller of the two top cards.
• Remove it from its pile, thereby exposing a new top card.
• Place the chosen card face-down onto the output pile.
• Repeatedly perform basic steps until one input pile is empty.
• Once one input pile empties, just take the remaining input pile and place it
face-down onto the output pile.
• Each basic step should take constant time, since we check just the two top cards.
• There are ≤ n basic steps, since each basic step removes one card from the
input piles, and we started with n cards in the input piles.
• Therefore, this procedure should take (n) time.
We don’t actually need to check whether a pile is empty before each basic step.
• Put on the bottom of each input pile a special sentinel card.
• It contains a special value that we use to simplify the code.
• We use ∞, since that’s guaranteed to “lose” to any other value.
• The only way that ∞ cannot lose is when both piles have ∞ exposed as their
top cards.
• But when that happens, all the nonsentinel cards have already been placed into
the output pile.
• We know in advance that there are exactly r − p + 1 nonsentinel cards ⇒stop
once we have performed r − p + 1 basic steps. Never a need to check for
sentinels, since they’ll always lose.
• Rather than even counting basic steps, just Þll up the output array from index p
up through and including index r .
Pseudocode:
MERGE(A, p, q, r )
n1 ← q − p + 1
n2 ←r − q
create arrays L[1 . . n1 + 1] and R[1 . . n2 + 1]
for i ← 1 to n1
do L[i ] ← A[p + i − 1]
for j ← 1 to n2
do R[ j ] ← A[q + j ]
L[n1 + 1]←∞
R[n2 + 1]←∞
i ← 1
j ← 1
for k ← p to r
do if L[i ] ≤ R[ j ]
then A[k] ← L[i ]
i ←i + 1
else A[k] ← R[ j ]
j ← j + 1
[The book uses a loop invariant to establish that MERGE works correctly. In a
lecture situation, it is probably better to use an example to show that the procedure
works correctly.]
Example: A call of MERGE(9, 12, 16)
[Read this Þgure row by row. The Þrst part shows the arrays at the start of the
“for k ← p to r” loop, where A[p . . q] is copied into L[1 . . n1] and A[q+1 . . r ] is
copied into R[1 . . n2]. Succeeding parts show the situation at the start of successive
iterations. Entries in A with slashes have had their values copied to either L or R
and have not had a value copied back in yet. Entries in L and R with slashes have
been copied back into A. The last part shows that the subarrays are merged back
into A[p . . r ], which is now sorted, and that only the sentinels (∞) are exposed in
the arrays L and R.]
Running time: The Þrst two for loops take O(n1 +n2) = O(n) time. The last for
loop makes n iterations, each taking constant time, for O(n) time.
Total time: O(n).
