## Theory of Combinatorial Algorithms

Prof. Emo Welzl and Prof. Bernd Gärtner

// 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