#include <stdio.h>
#include <math.h>
#define N 1000

void quicksort(float *data, int start, int end);
void merge(float *data1, int length1, float *data2, int length2,
  float *newlist);

/**************************************************************************/
/* Purpose: This program reads a list of numbers, divides the list into   */
/*  two sublists, performs a quicksort on each sublist, then merges the   */
/*  two sorted lists of numbers to form a single sorted list.             */
/**************************************************************************/

FILE *datafile; /* pointer to data file */

void main(int argc, char *argv[])
{
  char temp[60];
  int i, midpoint;
  float data1[N/2+1], data2[N/2+1], newlist[N];

  strcpy(temp, argv[1]);

  /* open data file */
  datafile = fopen(temp,"r");
  if (!datafile)
  {
    printf("*** Error opening %s ***\n",temp);
    exit(1);
  }

  midpoint = N/2;

  /* read entries from data file, storing first half in data1 
     and second half in data2 */
  for (i=0; i<midpoint; i++)
    fscanf(datafile,"%f\n",&data1[i]);
  for (i=midpoint; i<N; i++)
    fscanf(datafile,"%f\n",&data2[i-midpoint]);

  /* perform quicksort on each list */
  quicksort(data1,0,midpoint-1);
  quicksort(data2,0,N-1-midpoint);

  /* merge the two sublists */
  merge(data1,midpoint,data2,N-midpoint,newlist);

  /* print the sorted list */
  for (i=0;i<N;++i)
    printf("%f\n",newlist[i]);

  fclose(datafile);
  exit(1);
}

void quicksort(float *data, int begin, int end)
{
  /***********************************************************************/
  /* Purpose: sorts a list of numbers in increasing order                */
  /* Input:                                                              */
  /*   data: an unsorted array of numbers                                */
  /*   begin: the beginning index of "data"                              */
  /*   end: the final index of "data"                                    */
  /* Output:                                                             */
  /*   upon termination of the subroutine, "data" contains the sorted    */
  /*     list of numbers                                                 */
  /***********************************************************************/

  int leftarrow, rightarrow;
  float temp, pivot;

  leftarrow = begin;
  rightarrow = end;
  pivot = data[(begin+end)/2];
  while (1)
  {
    while (data[rightarrow] > pivot)
      rightarrow = rightarrow - 1;

    while (data[leftarrow] < pivot)
      leftarrow = leftarrow + 1;

    if (leftarrow <= rightarrow)
    {
      temp = data[leftarrow];
      data[leftarrow] = data[rightarrow];
      data[rightarrow] = temp;
      leftarrow = leftarrow + 1;
      rightarrow = rightarrow - 1;
    }

    if (rightarrow < leftarrow)
      break;
  } 

  if (begin < rightarrow)
    quicksort(data,begin,rightarrow);
  if (leftarrow < end)
    quicksort(data,leftarrow,end);

  return;
}

void merge(float *data1, int length1, float *data2, int length2,
  float *newlist)
{
  /***********************************************************************/
  /* Purpose: merges two sorted sublists (in increasing order) to form   */
  /*   a single sorted list                                              */
  /* Input:                                                              */
  /*   data1: a sorted array of numbers                                  */
  /*   length1: the length of array data1                                */
  /*   data2: a second sorted array of numbers                           */
  /*   length2: the length of array data2                                */
  /* Output:                                                             */
  /*   upon termination of the subroutine, "newlist" contains the        */
  /*     merged list of numbers, sorted in increasing order              */
  /***********************************************************************/

  int leftarrow1, rightarrow1, leftarrow2, rightarrow2, i;

  /* initialize variables */
  leftarrow1 = 0;
  rightarrow1 = length1-1;
  leftarrow2 = 0;
  rightarrow2 = length2-1;
  i=0;
  
  /* while both arrays are nonempty, copy the smallest element 
     appearing in either array, into newlist */
  while ((leftarrow1 <= rightarrow1) && (leftarrow2 <= rightarrow2))
  {
    if (data1[leftarrow1] < data2[leftarrow2])
    {
      newlist[i] = data1[leftarrow1];
      leftarrow1++;
    }
    else
    {
      newlist[i] = data2[leftarrow2];
      leftarrow2++;
    }
    i++;
  }
 
  /* finish nonempty array data1, if necessary */
  while (leftarrow1 <= rightarrow1)
  {
    newlist[i] = data1[leftarrow1];
    leftarrow1++;
    i++;
  }

  /* finish nonempty array data2, if necessary */
  while (leftarrow2 <= rightarrow2)
  {
    newlist[i] = data2[leftarrow2];
    leftarrow2++;
    i++;
  }

  return;
}