Beautiful Mergesort

Effective data structures and programming is about putting simple blocks of logic together until the whole is larger than the sum of the parts. A great example is Mergesort. Mergesort is a beautiful algorithm to implement sorting in NlogN time (N being the number of elements being sorted). This is the asymptotic lower bound on sorting.


Mergesort brings together the concepts of recursion, divide-and-conquer, arrays, and pointers (when implemented in C). So here is to Jon Von Neumann and his fantastic invention of Merge sort.

#include <stdio.h>
/*
Simple Mergesort implementation by Sachin Agarwal
sachinkagarwal@gmail.com


 */
void PrintList(int list[], int stIndex, int endIndex)
/*
  Helper function - Print the elements of array list, between stIndex and endIndex
*/
{
  for(; stIndex <= endIndex;stIndex++)
    printf("%d ",list[stIndex]);
}

void Merge (int dataArray[], int stIndexL, int endIndexL, int stIndexR, int endIndexR) 
/*
  Merge two lists into a tempArray in sorted order; this tempArray is copied back to dataArray. 
*/
{
  int tempArray[endIndexL-stIndexL+1+endIndexR-stIndexR+1]; //temp storage
  int stL = stIndexL;
  int resultCtr = 0;
  while (stIndexL <= endIndexL) {
    if (stIndexR>endIndexR) {
      tempArray[resultCtr++]=dataArray[stIndexL++];
      continue;
    }
    if (dataArray[stIndexL] <= dataArray[stIndexR]) {
      tempArray[resultCtr++] = dataArray[stIndexL++];
    }
    else {
      tempArray[resultCtr++] = dataArray[stIndexR++];
    }
  }
  while (stIndexR <= endIndexR) {
    tempArray[resultCtr++] = dataArray[stIndexR++];
  }
  int ii = stL;
  for (; ii<=endIndexR;ii++)
    dataArray[ii] = tempArray[ii-stL];
}

void Mergesort(int dataArray[], int stIndex,int endIndex) 
/*
  Mergesort routine, divide into two halves, and then merge.
*/
{
  int midIndex = stIndex + (endIndex-stIndex)/2;
  if(stIndex<endIndex) {
    Mergesort(dataArray,stIndex,midIndex);
    Mergesort(dataArray,midIndex+1,endIndex);
    Merge(dataArray,stIndex,midIndex,midIndex+1,endIndex);
  }    
}

int main() {
  int dataArray [] = {5,3,7,8,1,6,9,2,0};
  int stIndex = 0;
  int endIndex = sizeof(dataArray)/sizeof(int) - 1;
  printf("\nUNSORTED DATA ARRAY: ");
  PrintList(dataArray,stIndex,endIndex);

  Mergesort(dataArray,stIndex,endIndex);
  printf("\nFINAL RESULT: ");
  PrintList(dataArray,stIndex,endIndex);
}