Merger Sort

Merge sort is a divide and conquer based sorting algorithm.The complexity of the merge sort algorithm is O(NlogN). most of the implementation of merge sort is stable sort. A sorting algorithm is said to be stable if it is maintaining the relative order of equal elements of input set. Below is the basic approach of merge sort.

1)Divide the array repeatedly into two halves
2)Stop dividing when there is single element left. By
fact, single element is already sorted.
3)Merges two already sorted sub arrays into one

The above figure shows the approach for merge sort. (image source from wikipedia). suppose we have list { 38, 27, 43, 3, 9, 82, 10 }; as from above figure. below is sample code in c which implements the merge sort approach.

```#include<stdio.h>

void print (int *arr, int size);
void merge (int *arr, int m, int r);

void split (int *arr, int length)
{
if (length == 1)
return;
int middle = length / 2;
int remaining = length - middle;
split (arr, middle); // split first half
split (arr + middle, remaining); // split 2nd half
merge(arr,middle,remaining); //merge
}

void merge (int *arr, int m, int r)
{
int temp[m + r];
int i = 0, j = 0;

while (i + j < m + r)
{
if (i < m && arr[i] <= arr[m + j] || i < m && j >= r)
temp[i + j] = arr[i++];

if (j < r && arr[m + j] < arr[i] || j < r && i >= m)
temp[i + j] = arr[m + j++];
}
int k;
for (k = 0; k < m + r; k++)
arr[k] = temp[k];
}

int main ()
{
int arr[] = { 38, 27, 43, 3, 9, 82, 10 };
int length = sizeof (arr) / sizeof (arr[0]);

/* print array before sort */
printf ("The unsorted list is:\n");
print (arr, length);

/* split the list */
split (arr, length);
printf ("The sorted list is:\n");
print (arr, length);
return 0;
}

void print (int *arr, int size)
{
int i;
for (i = 0; i < size; i++)
printf ("%d ", arr[i]);
printf ("\n");
return;
}```

Ref:

http://cs.fit.edu/~pkc/classes/writing/hw13/song.pdf

http://en.wikipedia.org/wiki/Merge_sort