// From the software distribution accompanying the textbook // "A Practical Introduction to Data Structures and Algorithm Analysis, // Third Edition (C++)" by Clifford A. Shaffer. // Source code Copyright (C) 2007-2011 by Clifford A. Shaffer. // Mergesort implementation and timing test driver // Mergesort implementation optimized to reverse the 2nd half, // so that there is no need to test for exhausted sublists #include "book.h" // Include comparator functions #include "compare.h" // Mergesort implementation optimized to reverse the 2nd half template void mergesort(E A[], E temp[], int left, int right) { if (left == right) return; int i, j, k, mid = (left+right)/2; mergesort(A, temp, left, mid); mergesort(A, temp, mid+1, right); // Do the merge operation. First, copy 2 halves to temp. for (i=left; i<=mid; i++) temp[i] = A[i]; for (j=1; j<=right-mid; j++) temp[right-j+1] = A[j+mid]; // Merge sublists back to A for (i=left,j=right,k=left; k<=right; k++) if (Comp::prior(temp[i], temp[j])) A[k] = temp[i++]; else A[k] = temp[j--]; } template void sort(E* array, int n) { static E* temp = NULL; if (temp == NULL) temp = new E[n]; // Declare temp array mergesort(array, temp, 0, n-1); } #include "sortmain.cpp" int main(int argc, char** argv) { return sortmain(argc, argv); }