1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 //This is the file sortpatterncpp template <class T> int split(T a[], int begin, int end); //Rearranges elements [begin, end) of array a into two intervals //[begin, splitPt) and [splitPt, end), such that the Sorting pattern works //Returns splitPt template <class T> void join(T a[], int begin, int splitPt, int end); //Combines the elements in the two intervals [begin, split) and //[splitPt, end) in such a way that the Sorting pattern works template <class T> void sort(T a[], int begin, int end) //Precondition: Interval [begin, end) of a has elements //Postcondition: The values in the interval [begin, end) have //been rearranged so that a[0] <= a[1] <= <= a[(end - begin) - 1] { if ((end - begin) > 1) { int splitPt = split(a, begin, end); sort(a, begin, splitPt); sort(a, splitPt, end); join(a, begin, splitPt, end); }//else sorting one (or fewer) elements, so do nothing } template <class T> void sort(T a[], int numberUsed) //Precondition: numberUsed <= declared size of the array a //The array elements a[0] through a[numberUsed - 1] have values //Postcondition: The values of a[0] through a[numberUsed - 1] have //been rearranged so that a[0] <= a[1] <= <= a[numberUsed - 1] { sort(a, 0, numberUsed); }

Display 203 Merge Sort Realization of Sort Pattern (part 1 of 2)

1 2 3 4 5 6 //File mergesortcpp: the merge sort realization of the Sorting pattern template <class T> int split(T a[], int begin, int end) { return ((begin + end)/2); }

Display 203 Merge Sort Realization of Sort Pattern (part 2 of 2)

7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 template <class T> void join(T a[], int begin, int splitPt, int end) { T *temp; int intervalSize = (end - begin); temp = new T[intervalSize]; int nextLeft = begin; //index for first chunk int nextRight = splitPt; //index for second chunk int i = 0; //index for temp //Merge till one side is exhausted: while ((nextLeft < splitPt) && (nextRight < end)) { if (a[nextLeft] < a[nextRight]) { temp[i] = a[nextLeft]; i++; nextLeft++; } else { temp[i] = a[nextRight]; i++; nextRight++; } }

while (nextLeft < splitPt)//Copy rest of left chunk, if any { temp[i] = a[nextLeft]; i++; nextLeft++; } while (nextRight < end) //Copy rest of right chunk, if any { temp[i] = a[nextRight]; i++; nextRight++; } for (i = 0; i < intervalSize; i++) a[begin + i] = temp[i]; }

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 //Tests the Divide-and-Conquer Sorting pattern #include <iostream> using std::cout; using std::cin; using std::endl; #include "sortpatterncpp" #include "mergesortcpp" void fillArray(int a[], int //Precondition: size is the //Postcondition: numberUsed //a[0] through a[numberUsed //nonnegative integers read size, int& numberUsed); declared size of the array a is the number of values stored in a - 1] have been filled with from the keyboard

int main( ) { cout << "This program sorts numbers from lowest to highest\n"; int sampleArray[10], numberUsed; fillArray(sampleArray, 10, numberUsed); sort(sampleArray, numberUsed); cout << "In sorted order the numbers are:\n"; for (int index = 0; index < numberUsed; index++) cout << sampleArray[index] << " "; cout << endl; return 0; } void fillArray(int a[], int size, int& numberUsed) <The rest of the definition of fillArray is given in Display 55>