/* Merge sort and quick sort example program                           */
/* Version 1.01, last modified March 8, 1999, by Rick Wagner           */

#include <stdio.h>
#include <stdlib.h>              /* for rand() and RAND_MAX (= 32767)  */

int about();
void menu(int iArray[], int iMergeArray[], int n, int f);
void generateArray(int iArray[], int n);
void mergeSort(int iArrayA[], int iArrayB[], int l, int r);
void quickSort(int in[], int a, int b, int out[]);
void showArray(int iArray[], int n);

void main()
{
  int iArraySize = 100;
  int iArray[100];
  int iMergeArray[100];
  int iMerge = 0;                /* Flag for merge sort (default is quick sort) */

  iMerge = about();
  menu(iArray, iMergeArray, iArraySize, iMerge);
}

int about()
{
  int r = 0;
  char cChoice = '0';

  puts("                This program demonstrates merge sorting");
  puts("                    of an array of random integers.\n");
  puts("What sort of sorting would you like to do this session?\n");
  puts("a. Merge Sort.");
  puts("b. Quick Sort.\n");
  printf("Enter your choice: ");
  fflush(stdin);
  scanf("%c", &cChoice);
  if (cChoice == 'a') r = 1;

  return r;
}

void menu(int iArray[], int iMergeArray[], int n, int f)
{
  char cChoice = 'a';
  int i = 0;

  while (cChoice == 'a')
  {
    printf("a. Continue.            ");
    printf("b. Quit.                         ");
    printf("Enter your choice: ");
    fflush(stdin);
    scanf("%c", &cChoice);
    if (cChoice == 'a')
    {
      generateArray(iArray, n);
      printf("This is the unsorted array:\n");
      showArray(iArray, n);
      if (f)
      {
        mergeSort(iArray, iMergeArray, 0, n - 1);
      }
      else
      {
        quickSort(iArray, 0, n - 1, iMergeArray);
        for (i = 0; i < n; i++)                      /* Put the out array into the in array */
        {
          iArray[i] = iMergeArray[i];
        }
      }
      printf("This is the sorted array:\n");
      showArray(iArray, n);
    }
  } /* End of while() */
  puts("");
}

void generateArray(int iArray[], int n)
{
  int i = 0;
  float sfRand = 0;

  for (i = 0; i < n; i++)
  {
    sfRand = (((float) rand()) * 1000)  / ((float) RAND_MAX);
    iArray[i] = (int) sfRand;
  }
}

void showArray(int iArray[], int n)
{
  int i = 0;
  for (i = 0; i < n; i++)
  {
    printf("%5d", iArray[i]);
    if ((i + 1) % 10 == 0) printf("\n");
  }
  printf("\n");
}

/* This function is adapted from Sedgewick's Algorithms, p. 166. */
void mergeSort(int iArrayA[], int iArrayB[], int l, int r)
{
  int i = 0;
  int j = 0;
  int k = 0;
  int m = 0;
  int iMinI = 0;
  int iMaxJ = 0;
  
  if (r - l > 0)
  {
    m = (r + l) / 2;              /* integer division */
    mergeSort(iArrayA, iArrayB, l, m);
    mergeSort(iArrayA, iArrayB, m + 1, r);
    iMinI = m;
    for (i = m; i >= l; i--)
    {
      iArrayB[i] = iArrayA[i];
      iMinI = i;
    }
    iMaxJ = m + l;
    for (j = m + 1; j <= r; j++)
    {
      iArrayB[r + m + 1 - j] = iArrayA[j];
      iMaxJ = j;
    }
    for (k = l; k <= r; k++)
    {
      if (iArrayB[iMinI] < iArrayB[iMaxJ])
      {
        iArrayA[k] = iArrayB[iMinI];
        iMinI++;
      }
      else
      {
        iArrayA[k] = iArrayB[iMaxJ];
        iMaxJ--;
      }
    }
  }
}

/* This function is adapted from Structured C for Engineering and Technology, p. 403. */
void quickSort(int in[], int a, int b, int out[])
{
  int pivot;                                  /* Holder for array value.              */
  int i = 0;                                  /* i, j, k, and z are array indices.    */
  int j = 0;
  int k = 1;                                  /* k starts at one because our pivot is */
  int z = 0;                                  /* always at the zeroeth index in this version. */
  int in1[100], in2[100];                     /* Fixed array size for copying.        */
  int out1[100], out2[100];

  if(b != -1)                                 /* Just one element? Do nothing,        */
  {                                           /* ending the recursion.                */
    if(a == b)
    {
      out[0] = in[a];
    }
    else
    {
      /* Only two elements? They may need to be swappped. */
      if(1 == (b - a))
      {
        if(in[a] <= in[b])                    /* Do not swap. */
        {
          out[0] = in[a];
          out[1] = in[b];
        }
        else                                  /* Swap them. */
        {
          out[0] = in[b];
          out[1] = in[a];
        }
      }
      else                                    /* Handle 3-or-more elements. */
      {
        pivot = in[0];                        /* Pick first element for pivot. */
        while(k <= b)
        {
          /* Choose an output array to write to. */
          if(pivot > in[k])                   /* Compare pivot. */
          {
            /* Write smaller output array. */
            in1[i] = in[k];
            i++;
          }
          else                                /* Pivot is smaller. */
          {
            /* Write larger output array. */
            in2[j] = in[k];
            j++;
          }
          k++;                                /* Adjust input pointer. */
        }

        /* Sort smaller partition. */
        quickSort(in1, 0, i-1, out1);

        /* Sort larger partition. */
        quickSort(in2, 0, j-1, out2);

        /* Write smaller array to output. */
        for(k = 0; k < i; k++)
        {
          out[z] = out1[k];
          z++;
        }
        out[z] = pivot;                       /* Write pivot to output. */
        z++;

        /* Write larger array to output. */
        for(k = 0; k < j; k++)
        {
          out[z] = out2[k];
          z++;
        }
      }
    }
  }
}