/*********************************************************
*   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 <stdio.h>
#include <math.h>

  /*****************************************************
  * 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.     *
  * Output:                                            *
  *         a :  Table sorted in ascending order.      *
  *****************************************************/
  void sort(double *a, int lo, int hi) {

	if (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<n; i++) {
	  printf(" %5.2f ",a[i]);
	  if(i==7) printf("\n");
    }

    sort(a,0, n-1);

    printf("\n\n Sorted table A:\n");
    for(i=0; i<n; i++) {
	  printf(" %5.2f ",a[i]);
	  if(i==7) printf("\n");
    }
    printf("\n\n");
  }

//end of file msort.cpp