Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
/*
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];
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment