// 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 // Basic Mergesort version #include "book.h" // Include comparator functions #include "compare.h" // Basic mergesort implementation template void mergesort(E A[], E temp[], int left, int right) { if (left == right) return; // List of one element int mid = (left+right)/2; mergesort(A, temp, left, mid); mergesort(A, temp, mid+1, right); for (int i=left; i<=right; i++) // Copy subarray to temp temp[i] = A[i]; // Do the merge operation back to A int i1 = left; int i2 = mid + 1; for (int curr=left; curr<=right; curr++) { if (i1 == mid+1) // Left sublist exhausted A[curr] = temp[i2++]; else if (i2 > right) // Right sublist exhausted A[curr] = temp[i1++]; else if (Comp::prior(temp[i1], temp[i2])) A[curr] = temp[i1++]; else A[curr] = temp[i2++]; } } 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); }