// Prog: merge_sort.cpp
// implements and tests merge-sort on random input
#include
#include
// PRE: [first, middle), [middle, last) are valid ranges; in
// both of them, the elements are in ascending order
void merge (int* first, int* middle, int* last)
{
const int n = last - first; // total number of cards
int* const deck = new int[n]; // new deck to be built
int* left = first; // top card of left deck
int* right = middle; // top card of right deck
for (int* d = deck; d != deck + n; ++d)
// put next card onto new deck
if (left == middle) *d = *right++; // left deck is empty
else if (right == last) *d = *left++; // right deck is empty
else if (*left < *right) *d = *left++; // smaller top card left
else *d = *right++; // smaller top card right
// copy new deck back into [first, last)
const int* d = deck;
while (first != middle) *first++ = *d++;
while (middle != last) *middle++ = *d++;
delete[] deck;
}
// PRE: [first, last) is a valid range
// POST: the elements *p, p in [first, last) are in ascending order
void merge_sort (int* first, int* last)
{
const int n = last - first;
if (n <= 1) return; // nothing to do
int* const middle = first + n/2;
merge_sort (first, middle); // sort first half
merge_sort (middle, last); // sort second half
merge (first, middle, last); // merge both halfs
}
int main()
{
// input of number of values to be sorted
unsigned int n;
std::cin >> n;
int* const a = new int[n];
std::cout << "Sorting " << n << " integers...\n";
// create sequence:
for (int i=0; i
