// File: Sorting/mergesort.C
// Indirect merge sort (see Sedgewick, Chapter 12)
// Programmer: E. Kaltofen (September 27, 1992)
// Modified by: Mohan Nibhanupudi (Sept 21, 1994)
//              (pass l,r as range of sorting; assume index array is allocated)
#include <iostream.h>

typedef int ElType; // for testing purposes
extern int indir_insort(ElType[], int, int[]);

const int BREAKEVEN = 10; // size at which insertion sort is faster
                          // must be >= 1!

int indir_mergesort(ElType A[], int l, int r, int I[])
// set the array I[l],...,I[r] such that 
// A[I[l]] < A[I[l+1]] < ... < A[I[r]]
// note: one must have ElType operator<(ElType)
// returns the number of comparisons
{int mid, comp=0, i1, i2;

  // Escape from recursion;
#ifdef ESCAPE_TO_INSORT
  if((r-l+1) <= BREAKEVEN) 
    {
      comp = indir_insort(&A[l], r-l+1, &I[l]);
      //Translate the indices;
      int k;
      for(k=l;k<=r;k++) I[k] += l;
      return(comp);
    };
#else
  if(r-l <= 0)
    {
      I[l] = l;
      return comp;
    }
#endif

  // "sort" I by using the comparison I[i] "<" I[j] if A[I[i]] "<" A[I[j]];

  mid = (l+r)/2;
  // Sort segments l...mid and mid+1...r recursively;
  // note: 0<l<=r, so 0 <l<= mid <= r;

  int *Itemp = new int[r+1];
  comp += indir_mergesort( A, l, mid,   Itemp );
  comp += indir_mergesort( A, mid+1, r, Itemp );

  // Merge the sorted segments together (indirectly);
  int j = l-1; // starting index in merged segment;
  for(i1 = l, i2 = mid+1; // starting indices in each segment;
      i1 <= mid && i2 <= r; // still elements left in both segments?;
      comp++)
    if (A[ Itemp[i2] ] < A[ Itemp[i1] ]) // A[ I2[i2] ] goes into sorted array next
      I[++j] = Itemp[i2++];
    else // A[ I[i1] ] goes into sorted array next
      I[++j] = Itemp[i1++];

  // Complete segment with leftovers;
  if (i1 <= mid)
    for( ; i1 <= mid; i1++) I[++j] = Itemp[i1];
  else
    for( ; i2 <= r; i2++) I[++j] = Itemp[i2];

  delete[] Itemp;

  return(comp);
}// end indir_mergesort