*****************************************************************
* File: Mergesort.hh
* Author: Keith Schwarz ()
*
* An implementation of the Mergesort algorithm. This algorithm
* is implemented with a focus on readability and clarity rather
* than speed. Ideally, this should give you a better sense
* for how Mergesort works, which you can then use as a starting
* point for implementing a more optimized version of the algorithm.
*
* In case you are not familiar with Mergesort, the idea behind the
* algorithm is as follows. Given an input list, we wish to sort
* the list from lowest to highest. To do so, we split the list
* in half, recursively sort each half, and then use a merge algorithm
* to combine the two lists back together. As a base case for
* the recursion, a list with zero or one elements in it is trivially
* sorted.
*
* The only tricky part of this algorithm is the merge step, which
* takes the two sorted halves of the list and combines them together
* into a single sorted list. The idea behind this algorithm is
* as follows. Given the two lists, we look at the first element of
* each, remove the smaller of the two, and place it as the first
* element of the overall sorted sequence. We then repeat this
* process to find the second element, then the third, etc. For
* example, given the lists 1 2 5 8 and 3 4 7 9, the merge
* step would work as follows:
*
* FIRST LIST SECOND LIST OUTPUT
* 1 2 5 8 3 4 7 9
*
* FIRST LIST SECOND LIST OUTPUT
* 2 5 8 3 4 7 9 1
*
* FIRST LIST SECOND LIST OUTPUT
* 5 8 3 4 7 9 1 2
*
* FIRST LIST SECOND LIST OUTPUT
* 5 8 4 7 9 1 2 3
*
* FIRST LIST SECOND LIST OUTPUT
* 5 8 7 9 1 2 3 4
*
* FIRST LIST SECOND LIST OUTPUT
* 8 7 9 1 2 3 4 5
*
* FIRST LIST SECOND LIST OUTPUT
* 8 9 1 2 3 4 5 7
*
* FIRST LIST SECOND LIST OUTPUT
* 9 1 2 3 4 5 7 8
*
* FIRST LIST SECOND LIST OUTPUT
* 1 2 3 4 5 7 8 9
*
* The merge step runs in time O(N), and so using the Master Theorem
* Mergesort can be shown to run in O(N lg N), which is asymptotically
* optimal for a comparison sort.
*
* Our implementation sorts elements stored in std::vectors, since
* it abstracts away from the complexity of the memory management for
* allocating the scratch arrays.
*/
#ifndef Mergesort_Included
#define Mergesort_Included
#include
#include
/**
* Function: Mergesort(vector& elems);
* Usage: Mergesort(myVector);
* ---------------------------------------------------
* Applies the Mergesort algorithm to sort an array in
* ascending order.
*/
template
void Mergesort(std::vector& elems);
/**
* Function: Mergesort(vector& elems, Comparator comp);
* Usage: Mergesort(myVector, std::greater());
* ---------------------------------------------------
* Applies the Mergesort algorithm to sort an array in
* ascending order according to the specified
* comparison object. The comparator comp should take
* in two objects of type T and return true if the first
* argument is strictly less than the second.
*/
template
void Mergesort(std::vector& elems, Comparator comp);
/* * * * * Implementation Below This Point * * * * */
/* We store all of the helper functions in this detail namespace to avoid cluttering
* the default namespace with implementation details.
*/
namespace detail {
/* Given vectors 'one' and 'two' sorted in ascending order according to comparator
* comp, returns the sorted sequence formed by merging the two sequences.
*/
template
std::vector Merge(const std::vector& one, const std::vector& two, Comparator comp) {
/* We will maintain two indices into the sorted vectors corresponding to
* where the next unchosen element of each list is. Whenever we pick
* one of the elements from the list, we'll bump its corresponding index
* up by one.
*/
size_t onePos = 0, twoPos = 0;
/* The resulting vector. */
std::vector result;
/* For efficiency's sake, reserve space in the result vector to hold all of
* the elements in the two vectors. To be truly efficient, we should probably
* take in as another parameter an existing vector to write to, but doing so
* would complicate this implementation unnecessarily.
*/
result.reserve(one.size() + two.size());
/* The main loop of this algorithm continuously polls the first and second
* list for the next value, putting the smaller of the two into the output
* list. This loop stops once one of the lists is completely exhausted
* so that we don't try reading off the end of one of the lists.
*/
while (onePos < one.size() && twoPos < two.size()) {
/* If the first element of list one is less than the first element of
* list two, put it into the output sequence.
*/
if (comp(one[onePos], two[twoPos])) {
result.push_back(one[onePos]);
/* Also bump onePos since we just consumed the element at that
* position.
*/
++onePos;
}
/* Otherwise, either the two are equal or the second element is smaller
* than the first. In either case, put the first element of the second
* sequence into the result.
*/
else {
result.push_back(two[twoPos]);
++twoPos;
}
}
/* At this point, one of the sequences has been exhausted. We should
* therefore put whatever is left of the other sequence into the
* output sequence. We do this by having two loops which consume the
* rest of both sequences, putting the elements into the result. Of these
* two loops, only one will execute, although it isn't immediately
* obvious from the code itself.
*/
for (; onePos < one.size(); ++onePos)
result.push_back(one[onePos]);
for (; twoPos < two.size(); ++twoPos)
result.push_back(two[twoPos]);
/* We now have merged all of the elements together, so we can safely
* return the resulting sequence.
*/
return result;
}
}
/* Implementation of Mergesort itself. */
template
void Mergesort(std::vector& elems, Comparator comp) {
/* If the sequence has fewer than two elements, it is trivially in sorted
* order and we can return without any more processing.
*/
if (elems.size() < 2)
return;
/* Break the list into a left and right sublist. */
std::vector left, right;
/* The left half are elements [0, elems.size() / 2). */
for (size_t i = 0; i < elems.size() / 2; ++i)
left.push_back(elems[i]);
/* The right half are the elements [elems.size() / 2, elems.size()). */
for (size_t i = elems.size() / 2; i < elems.size(); ++i)
right.push_back(elems[i]);
/* Mergesort each half. */
Mergesort(left, comp);
Mergesort(right, comp);
/* Merge the two halves together. */
elems = detail::Merge(left, right, comp);
}
/* The Mergesort implementation that does not require a comparator is implemented
* in terms of the Mergesort that does use a comparator by passing in std::less.
*/
template
void Mergesort(std::vector& elems) {
Mergesort(elems, std::less());
}
#endif
Keep. Track. Share.
