/* From: [D.A.]  7/1999

   A Version of Merge-Sort.

   The `list' terminology is unfortunate because it has nothing
   to do with linked-lists at all;  this one sorts an array.
   (You can find a merge-sort for linked-lists under .../C/List/ )

   Note that it is slightly more efficient, probably more common,
   to allocate the extra working-storage once only before the routine
   starts and free it all at the end rather than allocate and
   free storage repeatedly.
   Exercise: how much space does the version below allocate and free?

   - LA
*/

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

int* mergeLists(int a[], int aSize, int b[], int bSize);

/*
 *  Sort a list of integers into increasing order.
 */
void 
mergeSort(int list[], int size)
{
  int mid = size/2;
  int* tmp = NULL;
  int i;

  if (size > 1)
  {
     mergeSort(&list[0], mid);
     mergeSort(&list[mid], size-mid);
    
     tmp = mergeLists(&list[0], mid, &list[mid], size-mid);
     
     if (tmp != NULL)
     {
        for (i = 0; i < size; i++)
        {
           list[i] = tmp[i];  /* copy lists */
        }
     }
     
     free(tmp);
  }
}


/*
 *  Merges two sorted integer lists into a new list, and
 *  returns a pointer to the new list.
 */
int* 
mergeLists(int a[], int aSize, int b[], int bSize)
{
  int i = 0;
  int j = 0;
  int k;
  int* newList = (int*)malloc((aSize + bSize)*sizeof(int));

  if (newList != NULL)
  {
     for (k = 0; k < aSize + bSize; k++)
     {
         if (i == aSize)
         {
            newList[k] = b[j];
            j++;
         } 
         else if (j == bSize)
         {
            newList[k] = a[i];
            i++;
         }
         else if (a[i] <= b[j])
         {
            newList[k] = a[i];
            i++;
         }
         else
         {
            newList[k] = b[j];
            j++;
         }
     }
  }
  else
  {
     fprintf(stderr, "Out of memory");
     exit(1);
  }

  return newList;
}