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

void merge(int [], int, int, int);
void mergesort(int *, int, int);

#define SIZE 10

int main(void)
{
  int arr[SIZE] = {125, 52, 34, 80, 200, 12, 29, 102, 53, 89};

  // Sort the entire array (from index 0 to index SIZE-1)
  mergesort(arr, 0, SIZE-1);

  for (int i = 0; i < SIZE; i++)
  {
    if (i == SIZE-1)
      printf("%d\n", arr[i]);
    else
      printf("%d, ", arr[i]);
  }
}

/*
 * This is the merge routine used by mergesort
 *
 * This assumes that the items in list from indexFirst to indexMiddle,
 * and the items from indexMiddle+1 to indexLast, have already been sorted.
 * The routine merges the two sorted sequences together,
 * It dynamically allocates just enough memory to do the merge.
 */
void merge(int list[], int indexFirst, int indexMiddle, int indexLast)
{
  int *p1, *p2;
  int *pCopy;
  int count = 0;

  pCopy = (int *) malloc(sizeof(int) * (indexLast - indexFirst + 1));

  p1 = &list[indexFirst];
  p2 = &list[indexMiddle + 1];
  while (count < indexLast - indexFirst + 1)
  {
    if ((p1 <= &list[indexMiddle])
	&& ((p2 > &list[indexLast]) || (*p1 < *p2)))
    {
      pCopy[count] = *p1;
      p1++;
    }
    else
    {
      pCopy[count] = *p2;
      p2++;
    }
    count++;
  }

  for (count = 0; count < indexLast - indexFirst + 1; count++)
    list[indexFirst+count] = pCopy[count];

  free(pCopy);
}

/*
 * Sort an array of integers, from indexFirst to indexLast,
 * using mergeSort. This is a recursive sorting routine.
 */
void mergesort(int list[], int indexFirst, int indexLast)
{
  int indexMiddle;

  // If we are only dealing with one element, we don't need to do anything
  if (indexFirst >= indexLast)
    return;

  // Calculate the middle index
  indexMiddle = (indexFirst + indexLast) / 2;
  mergesort(list, indexFirst, indexMiddle); // Sort left half
  mergesort(list, indexMiddle + 1, indexLast); // Sort right half
  merge(list, indexFirst, indexMiddle, indexLast); // Merge sorted halves

  return;
}