// Program: sort_array3.C
// initialize an array of n numbers in descending
// order, and then sort them into ascending order,
// using a function (this is for measuring sorting
// time)
#include
#include
#include
// PRE: [first, last) is a valid range
// POST: the elements *p, p in [first, last) are in ascending order
void minimum_sort (int* first, int* last)
{
for (int* p = first; p != last; ++p) {
// find minimum in nonempty range described by [p, last)
int* p_min = p; // pointer to current minimum
int* q = p; // pointer to current element
while (++q != last)
if (*q < *p_min) p_min = q;
// interchange *p with *p_min
std::iter_swap (p, p_min);
}
}
// 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)
{
int n = last - first; // total number of cards
int* 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)
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)
{
int n = last - first;
if (n <= 1) return; // nothing to do
int* 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()
{
int n = 1600000; // number of values to be sorted
int* a = new int[n];
std::cout << "Sorting " << n << " integers...\n";
// create sequence: 0, n-1, 1, n-2,...
for (int i=0; i
