/* C, code from Numerical Recipes */
#include <time.h>
#include <stdlib.h>

#include <iostream.h>
#include <algo.h>

// 7 is the threshold defined in the book, so that's what I used
#define M 7
// 50 is the limit defined in the book, so that's what I used
#define NSTACK 50

void num_rec_sort(int n, TYPE arr[])
{
  // This code is from Numerical Recipes, with minor changes
  int i, ir=n, j, k, l=0, *istack;
  int jstack = 0;
  TYPE a;

  istack = new int[NSTACK]; // manage our own stack
  for(;;) {
    if(ir-l < M) { // Insertion sort when subarray small enough
      for(j=l+1; j<ir; j++) {
	a=arr[j];
	for(i=j-1; i>=1; i--) {
	  if(arr[i] <= a) break;
	  arr[i+1]=arr[i];
	}
	arr[i+1]=a;
      }
      if(jstack == 0) break;
      ir=istack[jstack--];
      l=istack[jstack--];
    } else {   // quicksort when the subarray is large
      k=(l+ir)>>1;
      swap(arr[k], arr[l+1]);
      if(arr[l] > arr[ir]) {
	swap(arr[l], arr[ir]);
      }
      if(arr[l+1] > arr[ir]) {
	swap(arr[l+1], arr[ir]);
      }
      if(arr[l] > arr[l+1]) {
	swap(arr[l], arr[l+1]);
      }
      i=l+1;
      j=ir;
      a=arr[l+1];
      for(;;) {
	do i++; while(arr[i] < a);
	do j--; while(arr[j] > a);
	if(j<i) break;
	swap(arr[i], arr[j]);
      }
      arr[l+1]=arr[j];
      arr[j]=a;
      jstack += 2;
      if(jstack > NSTACK) abort();
      if(ir-i+1 >= j-1) {
	istack[jstack]=ir;
	istack[jstack-1]=i;
	ir=j-1;
      } else {
	istack[jstack]=j-1;
	istack[jstack-1]=l;
	l=i;
      }
    }
  }
  delete[] istack;
}

void test(int N)
{
  if(N < 1)
  {
    cerr << "Input value " << N << " too small." << endl;
    return;
  }

  TYPE* data = new TYPE[N];
  if(!data)
  {
    cerr << "Could not allocate data - " << N << " bytes." << endl;
    return;
  }
  for(int i=0; i<N; ++i)
    data[i] = rand();

  time_t begin = clock();
  num_rec_sort(N, data);
  time_t end = clock();
  double time_elapsed = double(end-begin)/CLOCKS_PER_SEC;

  cout << time_elapsed << endl;
  delete[] data;
}

int main(int argc, char* argv[])
{
  if(argc != 2)
    cerr << "Usage: " << argv[0] << "<array-size>" << endl;
  else
  {
    for(int i=0; i<10; ++i)
      test(atoi(argv[1]));
  }
  return 0;
}