merge_sort_basic.c

// If you're having a hard time understanding merge sort
// like I am, hopefully this helps you understand the sort operation half.
// This program will print bound values through each recursive call.
// Don't get slipped up with the fact mergesort calls sort once
// in the beginning like I did.

// Also try to wrap your head around start bound (s_bound)
// and end bound (e_bound). In my case it helped me understand
// How the base case works to stop the recursion from happening
// forever. 




#include <stdio.h>





//-------------------------
// function prototypes
//-------------------------

void mergesort(int* array, int length);

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

void print_array(int* array,int length);




//-------------------------
// MAIN
//-------------------------

void main(void)
{
  // given an array and it's length
  
  int array[] = {1,2,3,4,5,6,7,8,9};
  int length = sizeof array/sizeof array[0];
  
  // sort the array using mergesort()
  
  mergesort(array, length);
  
  print_array(array, length);
}





//-------------------------
// sorting functions
//-------------------------


void mergesort(int* array, int length)
{
  // given an array and it's length
  // recursively run sort on halves until array is of size 1
  
  //{1,2,3,4,5,6,7,8}
  // l     m       r
  
  int mid = length/2;
  
  int ls = 0;
  int re = length-1;
  
  
  sort(array, 0, length-1);
  
}




void sort(int* array, int s_bound, int e_bound)
{
  printf("s_bound: %i | e_bound: %i\n", s_bound, e_bound);
  if (s_bound >= e_bound)
    return; // start the merging steps up the call stack
    
  int mid = (s_bound + e_bound)/2;
  
  int ls = s_bound;
  int re = e_bound;
  
  sort(array, ls, mid);
  sort(array, mid+1, re);
}




//-------------------------
// utility functions
//-------------------------

void print_array(int* array,int length)
{
  printf("[");
  for(int i = 0; i < length; i++)
  {
    if(i == length-1)
    {
      printf("%i", array[i]);
    }
    else
    {
      printf("%i, ", array[i]);  
    }
    
  }
  printf("]\n");
}