merge_sort.c

/*
Mergesort algorithm in C by John James Yzaguirre.

The mergesort algorithm was invented by John Von Neumann in 1945.
Worst case runtime of bigO(n log n).
The best and average case runtimes are also bigO(n log n)

Given a list
if list is of size 1 or 0 return. Otherwise
  split the list in half
  run mergesort on each half
merge the halfs together
*/

//--------------------------------------------------

#include <stdio.h>

void sort(int* array, int* temp, int s_bound, int e_bound);

void merge(int* array, int* temp, int mid, int s_bound, int e_bound);

void main(void)
{
  // Given an array of values
  
  int array[] = {7,6,5,4,3,2,1};
  int length = sizeof array/sizeof array[0];
  
  int temp[length];
  
  int s_bound = 0; // first index is the starting boundary
  
  int e_bound = length-1; // last index is the end boundary
  
  sort(array, temp, s_bound, e_bound);
  
  for (int i = 0; i <= e_bound; i++)
    printf("%i ", array[i]);
  printf("\n");
  
}

//----------------------
// merge sort functions
//----------------------

void sort(int* array, int* temp, int s_bound, int e_bound)
{
  /*
      First check if the array is proven to be sorted by
      being size 1 or zero.
      
      Given the s_bound and e_bound, 
      which are the indices of 1st and last array values,
      just check if s_bound is the same as e_bound (size 1)
      or greater (size 0). Size 0 can occur is we send values
      out of bounds. 
      
      side note: We might split an array and have a starting value
      that is plus 1 beyond the array and have the end bound be the actual
      end of the array.
  */
  
  if (s_bound >= e_bound)
    return;
    
  
  /*
      By applying the algorithm to the left and right halves,
      we are effectively splitting them up each time we go
      back around recursively.
  */
  
  /* 
      We need to know what middle is equal to in any case
      remember we might be somewhere within our array like 
      s_index = 7 and e_index = 10
      {1,2,3,4,5,6,7,8,9,10} right half is 7,8,9,10
      so to get the middle index of the right side, 
      we need (7 + 10) / 2 which would truncate 
      to 8 
  */
  
  int mid = (s_bound + e_bound) / 2;
  
  sort(array, temp, s_bound, mid);
  sort(array, temp, mid + 1, e_bound);
  
  /* 
      Now we're recusively splitting the array in half until we have
      array's of size 1. We know for a fact the array is "sorted" at
      this point. It's important to remember the algorithm relies on
      trusting at each step going back up the call stack, that the 
      values it is comparing on either side, are in their own right
      sorted halves. So when we have an array of size 1 comparing
      another array of size 1, we can compare trusting they are sorted.
      We then combine them, in sorted order. Now we have an array of size 2
      on each side, which merge assumes is sorted, so we compare values
      on each side until we have a merge array in sorted order. By doing
      this all the way up we finally have 2 sorted halves that when
      merged are a complete sorted array of values.
  */
  
  // passing in mid gives us both left_end and right_start (mid and mid + 1)
  
  merge(array, temp, mid, s_bound, e_bound);
  
}




void merge(int* array, int* temp, int mid, int s_bound, int e_bound)
{
  /*
    The details involve creating a temp array, for storing the sorted
    values, which then get copied back into the original array using the
    same indexes. So we need to keep track of the index of everything as
    we move around copying values. That means new variables for:
    left_index
    right_index
    index (the temp array)
  */
  
  int left_index = s_bound;
  int right_index = mid + 1;
  int index = s_bound;
  
  // while there are values on both sides to compare...
  while(left_index <= mid && right_index <= e_bound)
  {
    if (array[left_index] < array[right_index])
    {
      temp[index] = array[left_index];
      left_index++;
    }
    else
    {
      temp[index] = array[right_index];
      right_index++;
    }
    index++;
  }
  
  /*
      In some cases we might have left over values from one half,
      for example the left side might be less 3 times in a row,
      so it's going to run out of values to compare.
      When this happens, since we know both halves are sorted already,
      the left over values are proven to be sorted. So we can just copy
      them straight into the temp array from where we left off.
      It's important to keep track of the indicies here.
  */
  
  //copy left half values if there are any
  while(left_index <= mid)
  {
    temp[index] = array[left_index];
    left_index++;
    index++;
  }
  
  //copy right half values if there are any remaining
  while(right_index <= e_bound)
  {
    temp[index] = array[right_index];
    right_index++;
    index++;
  }
  
  //copy the entire temp array into the original array
  for(int i = s_bound; i <= e_bound; i++)
    array[i] = temp[i];
}