/********************************************************* * Demonstration Program of In-place Merge Sorting * * (about n*n comparisons used with no extra storage). * * ------------------------------------------------------ * * Reference: After a java algorithm By Jason Harrison, * * 1995 University of British Columbia. * * * * C++ Version By J-P Moreau, Paris. * * (www.jpmoreau.fr) * * ------------------------------------------------------ * * SAMPLE RUN: * * * * Initial table A: * * 4.00 3.00 1.00 67.00 55.00 8.00 0.00 4.00 * * -5.00 37.00 7.00 4.00 2.00 9.00 1.00 -1.00 * * * * Sorted table A: * * -5.00 -1.00 0.00 1.00 1.00 2.00 3.00 4.00 * * 4.00 4.00 7.00 8.00 9.00 37.00 55.00 67.00 * * * *********************************************************/ #include #include /***************************************************** * In-place sorting of a table a[] in ascending order * * -------------------------------------------------- * * Inputs: * * a : Table of n real numbers * * lo: Starting index (>=0) * * hi: Ending index (<=n-1), with lo=hi) return; //no action int mid = (lo + hi) / 2; // Partition the list into two lists and sort them recursively sort(a, lo, mid); sort(a, mid + 1, hi); // Merge the two sorted lists int start_hi = mid + 1; int end_lo = mid; while ((lo <= end_lo) && (start_hi <= hi)) { if (a[lo] < a[start_hi]) lo++; else { // a[lo] >= a[start_hi] // The next element comes from the second list, // move the a[start_hi] element into the next // position and shuffle all the other elements up. double T = a[start_hi]; for (int k = start_hi - 1; k >= lo; k--) { a[k+1] = a[k]; } a[lo] = T; lo++; end_lo++; start_hi++; } } } void main() { int i,n=16; static double a[] = {4,3,1,67,55,8,0,4,-5,37,7,4,2,9,1,-1}; printf("\n\n Initial table A:\n"); for(i=0; i