CSCI 362: Divide and Conquer (and Combine) Algorithms

namespace SortUtils
{

// Given a RandomAccessRange [first, last), determine where the "midpoint"
// would be and perform the following steps:
// order *first, *mid, *std::prev(last) in such a way such that
//   *first <= *mid <= *std::prev(last)
//
// returns the median value
//
template<std::random_access_iterator Iter>
std::iter_value_t<Iter>
median3 (Iter first, Iter last);


// Takes two sorted ranges [first1, last1) and [first2, last2)
// and "merges" them by copying values into the iterator starting
// at "out". Uses operator< for comparing values
//
// Returns the iterator of one-past-the-last where we wrote to out
//
template<typename Iter1, typename Iter2, typename OIter>
OIter
merge (Iter1 first1, Iter1 last1, Iter2 first2, Iter2 last2, OIter out);


// Takes a RandomAccessRange [first, last) and partitions the data into
// three groups -- this should be accomplished in a SINGLE PASS Big-O: O(N)
//
// Group 1: all values in [first, last) < pivot
// Group 2: all values in [first, last) == pivot
// Group 3: all values in [first, last) > pivot
//
// [ ... Group 1 ... | ... Group 2 ... | ... Group 3 ... ]
//                   ^                 ^
//                   p1                p2
//
// Returns a pair of iterators pointing to "p1" and "p2" above
//
template<typename Iter, typename Value>
std::pair<Iter, Iter>
partition (Iter first, Iter last, Value const& pivot);


// Given a RandomAccessRange, recursively call partition on either the
// left half or right half until you have found the nth largest element
//
// A call to nth_element (v.begin(), v.end(), 0) will return the min
// A call to nth_element (v.begin(), v.end(), v.size() - 1) will return the max
// A call to nth_element (v.begin(), v.end(), v.size() / 2) will return the median
//
// Precondition:
//   std::distance (begin, end) > n
//
// Hints:
//  - n will change if you need to recurse on the right half
//  - No recursion happens if "index of" n is between "index of" p1 and p2
//    remember: p1 and p2 are the return values to partition.
//  - call median3 to get a pivot value
//
template<typename Iter>
Iter
nth_element (Iter first, Iter last, size_t n);


// Given a RandomAccessRange, sort the range with merge_sort
//
// Behavior should be identical to std::sort
//
// Precondition:
//   std::distance (begin, end) > n
//
// Hints:
//  - You will need a local vector allocated to use as the "output" parameter for merge
//
template<typename Iter>
void
merge_sort (Iter first, Iter last);


// Given a RandomAccessRange, sort the range with quick_sort
//
// Behavior should be identical to std::sort
//
// Precondition:
//   std::distance (begin, end) > n
//
// Hints:
//  - call median3 to get a pivot value
//
template<typename Iter>
void
quick_sort (Iter first, Iter last);

} // end namespace SortUtils