Section 13.10 Mergesort
In
Section 13.7, we saw a simple sorting algorithm that turns out not to be very efficient. In order to sort
items, it has to traverse the vector
times, and each traversal takes an amount of time that is proportional to
The total time, therefore, is proportional to
In this section I will sketch a more efficient algorithm called
mergesort. To sort
items, mergesort takes time proportional to
That may not seem impressive, but as
gets big, the difference between
and
can be enormous. Try out a few values of
and see.
The basic idea behind mergesort is this: if you have two subdecks, each of which has been sorted, it is easy (and fast) to merge them into a single, sorted deck. Try this out with a deck of cards:
-
Form two subdecks with about 10 cards each and sort them so that when they are face up the lowest cards are on top. Place both decks face up in front of you.
-
Compare the top card from each deck and choose the lower one. Flip it over and add it to the merged deck.
-
Repeat step two until one of the decks is empty. Then take the remaining cards and add them to the merged deck.
The result should be a single sorted deck. Here’s what this looks like in pseudocode:
Deck merge(const Deck& d1, const Deck& d2) {
Deck result (d1.cards.size() + d2.cards.size());
int i = 0;
int j = 0;
for (size_t k = 0; k<result.cards.size(); k++) {
}
return result;
}
I chose to make
merge
a nonmember function because the two arguments are symmetric.
The best way to test
merge
is to build and shuffle a deck, use subdeck to form two (small) hands, and then use the sort routine from the previous chapter to sort the two halves. Then you can pass the two halves to
merge
to see if it works.
If you can get that working, try a simple implementation of
mergeSort
:
Deck Deck::mergeSort() const {
}
Notice that the current object is declared
const
because
mergeSort
does not modify it. Instead, it creates and returns a new
Deck
object.
If you get that version working, the real fun begins! The magical thing about mergesort is that it is recursive. At the point where you sort the subdecks, why should you invoke the old, slow version of
sort
? Why not invoke the spiffy new
mergeSort
you are in the process of writing?
Not only is that a good idea, it is
necessary in order to achieve the performance advantage I promised. In order to make it work, though, you have to add a base case so that it doesn’t recurse forever. A simple base case is a subdeck with 0 or 1 cards. If
mergesort
receives such a small subdeck, it can return it unmodified, since it is already sorted.
The recursive version of
mergesort
should look something like this:
Deck Deck::mergeSort(Deck deck) const {
}
As usual, there are two ways to think about recursive programs: you can think through the entire flow of execution, or you can make the “leap of faith.” I have deliberately constructed this example to encourage you to make the leap of faith.
When you were using
sort
to sort the subdecks, you didn’t feel compelled to follow the flow of execution, right? You just assumed that the
sort
function would work because you already debugged it. Well, all you did to make
mergeSort
recursive was replace one sort algorithm with another. There is no reason to read the program differently.
Well, actually you have to give some thought to getting the base case right and making sure that you reach it eventually, but other than that, writing the recursive version should be no problem. Good luck!
Checkpoint 13.10.1.
The efficiency of a simple sorting algorithm is __________. The efficiency of mergesort is __________. Mergesort is __________ than the simple sorting algorithm.
Simple sort traverses the vector n times, and each traversal takes additional time.
Simple sort takes time proporitonal to mergesort takes time proportional to (which is more efficient).
You might be confused about which algorithm is which. Also, what is the efficiency of simple sort?
You might be confused about which algorithm is which.
Which algorithm is more efficient? (Which function grows more slowly?)
Checkpoint 13.10.2.
Write your implementation of
merge
in the commented area of the active code below. Read the comments in
main
to see how we’ll test if your
merge
function works. If you get stuck, you can reveal the hint below for help.
Hint. merge
Activity 13.10.1.
First, let’s write the code for the merge function. merge should take two decks as parameters and return a deck with the deck merged.
Deck merge(const Deck& d1, const Deck& d2) {
---
void merge(const Deck& d1, const Deck& d2) { #paired
---
Deck result (d1.cards.size() + d2.cards.size());
---
size_t i = 0;
size_t j = 0;
---
for (size_t k = 0; k < result.cards.size(); ++k) {
---
if (d1.cards.empty()) {
result.cards[k] = d2.cards[j];
++j;
}
---
if (d1.cards.empty()) {
result.cards[k] = d1.cards[i];
++i;
} #paired
---
else if (d2.cards.empty()) {
result.cards[k] = d1.cards[i];
++i;
}
---
else if (d1.cards.empty()) {
result.cards[k] = d2.cards[j];
++j;
} #paired
---
else {
---
if (j >= d2.cards.size()) {
result.cards[k] = d1.cards[i];
++i;
}
---
else if (i >= d1.cards.size() || d1.cards[i].isGreater(d2.cards[j])) {
result.cards[k] = d2.cards[j];
++j;
}
---
else {
result.cards[k] = d1.cards[i];
++i;
}
}
---
}
return result;
}
Checkpoint 13.10.3.
Now that we’ve written
merge
, it’s time to write the
mergeSort
function. Try writing the non-recursive version of
mergeSort
first before writing the recursive version. Follow the comments in
main
to test your functions. If done correctly, the program should output a sorted deck of cards. If you get stuck, you can reveal the hints below for help.
Hint 1. mergeSort
Activity 13.10.2.
Let’s write the code for the mergeSort function. mergeSort should be a Deck member function that returns a sorted deck.
Deck Deck::mergeSort() const {
---
Deck mergeSort() { #paired
---
int mid = cards.size() / 2;
---
Deck d1 = subdeck(0, mid - 1);
Deck d2 = subdeck(mid, cards.size() - 1);
---
d1.sortDeck();
d2.sortDeck();
---
return merge(d1, d2);
}
Hint 2. mergeSort recursive
Activity 13.10.3.
Let’s take it one step further and rewrite
mergeSort
as a recursive function.
Deck Deck::mergeSort(Deck deck) const {
---
if (deck.cards.size() == 0 || deck.cards.size() == 1) {
return deck;
}
---
int mid = deck.cards.size() / 2;
---
Deck d1 = subdeck(0, mid - 1);
Deck d2 = subdeck(mid, deck.cards.size() - 1);
---
Deck merged1 = d1.mergeSort(d1);
Deck merged2 = d2.mergeSort(d2);
---
return merge(merged1, merged2);
}
You have attempted
1 of
7 activities on this page.