// 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. // Also, sublists of length <= THRESHOLD are sorted with insertion sort. #include "book.h" // Include comparator functions #include "compare.h" // Standard insertion sort implementation template void inssort(E A[], int n) { // Insertion Sort for (int i=1; i0) && (Comp::prior(A[j], A[j-1])); j--) swap(A, j, j-1); } extern int THRESHOLD; //Optimized mergesort implementation template void mergesort(E A[], E temp[], int left, int right) { if ((right-left) <= THRESHOLD) { // Small list inssort(&A[left], right-left+1); 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=mid; i>=left; 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); }