/*-------------------------------------------------------------------*/
/* testsort.c                                                        */
/* A program to demonstrate gprof                                    */
/*-------------------------------------------------------------------*/

#include <string.h>
#include <stdio.h>
#include <stdlib.h>

#define MAX_SIZE 1000000

void fillArray(int piArray[], int iSize)
{
   int i;
   for (i = 0; i < iSize; ++i)
      piArray[i] = rand();
}

void swap(int piArray[], int i1, int i2)
{
   int iTemp;
   iTemp = piArray[i1];
   piArray[i1] = piArray[i2];
   piArray[i2] = iTemp;
}

void sort(int piArray[], int iLeft, int iRight)
{
   int i;
   int iLast;

   if (iLeft >= iRight)
      return;
   
   swap(piArray, iLeft, (iLeft + iRight) / 2);
   iLast = iLeft;
   for (i = iLeft+1; i <= iRight; i++)
      if (piArray[i] < piArray[iLeft])
         swap(piArray, ++iLast, i);
   swap(piArray, iLeft, iLast);
   sort(piArray, iLeft, iLast-1);
   sort(piArray, iLast+1, iRight);
}

void printArray(int piArray[], int iSize)
{
   int i;
   for (i = 0; i < iSize; ++i)
      printf("%d\n", piArray[i]);
}

int main(int argc, char *argv[])
{
   int piArray[MAX_SIZE];

   fillArray(piArray, MAX_SIZE);
   sort(piArray, 0, MAX_SIZE);
/* printArray(piArray, MAX_SIZE); */
   return 0;
}