/**
 *  Iterative merge sort algorithm
 *
 *  @author:  Sartaj Sahni, ported to C++ by Timothy Rolfe
 *
 *  @see  Data Structures, Algorithms, and Applications in C++,
 *        pp. 680-81 (the original in C++ has a memory leak)
 *
 *  Minor revision by Timothy Rolfe (tjr) --- saves two comparisons
 */

#include <stdlib.h>
#include "MergeSort.h"  // Keep ourselves honest

 /**
  * Merge from one array into another
  */
void merge (int *c, int *d, int lt, int md, int rt)
{// Merge c[lt:md] and c[md+1:rt] to d[lt:rt]
   int i = lt,       // cursor for first segment
       j = md+1,     // cursor for second
       k = lt;       // cursor for result

// merge until i or j exits its segment
   while ( (i <= md) && (j <= rt) )
      if (c[i] <= c[j])  d[k++] = c[i++];
      else               d[k++] = c[j++];

// take care of left overs --- tjr code:  only one while loop actually runs
   while ( i <= md )
      d[k++] = c[i++];
   while ( j <= rt )
      d[k++] = c[j++];
} // end merge()

/**
 * Perform one pass through the two arrays, invoking Merge() above
 */
void mergePass (int *x, int *y, int s, int n)
{// Merge adjacent segments of size s.
   int i = 0, j;

   while (i <= n - 2 * s)
   {//Merge two adjacent segments of size s
      merge (x, y, i, i+s-1, i+2*s-1);
      i = i + 2*s;
   }
// fewer than 2s elements remain
   if (i + s < n)
      merge (x, y, i, i+s-1, n-1);
   else
      for (j = i; j <= n-1; j++)
         y[j] = x[j];   // copy last segment to y
} // end mergePass()

/**
 * Entry point for merge sort
 */
void mergeSort (int *a, int n)
{// Sort a[0:n-1] using merge sort.
   int  s = 1;      // segment size
   int *b = (int*) calloc ( n, sizeof(*b) );

   while (s < n)
   {  mergePass (a, b, s, n); // merge from a to b
      s += s;                 // double the segment size
      mergePass (b, a, s, n); // merge from b to a
      s += s;                 // again, double the segment size
   } // end while
   // return the scratch array b  --- tjr
   free (b);
}  // end mergeSort