# Merge Sort Algorithm And C Code

Merge sort is a sorting technique, which is  based on comparison sorting algorithm, having complexity O(n log n). It is one of the types of stable sort, meaning, that in its implementation, input order of equal elements is preserved in the sorted output.  It was invented by John von Neumann in 1945. Merge sort is a divide and conquer algorithm.

The concept of Merge Sort is based on the following principle:

Divide the unsorted list into 'n' sub-lists, each containing 1 element (a list of 1 element is considered sorted).
Repeatedly merge sub-lists to produce new sub-lists until there is only 1 sub-list remaining. This will be the sorted list.

## Algorithm for Merge Sort:

```/* Double-Click To Select Code */

function merge_sort(list m)
// if list size is 0 (empty) or 1, consider it sorted and return it
// (using less than or equal prevents infinite recursion for a zero length m)
if length(m) <= 1
return m
// else list size is > 1, so split the list into two sublists
var list left, right
var integer middle = length(m) / 2
for each x in m before middle
for each x in m after or equal middle
// recursively call merge_sort() to further split each sublist
// until sublist size is 1
left = merge_sort(left)
right = merge_sort(right)
// merge the sublists returned from prior calls to merge_sort()
// and return the resulting merged sublist
return merge(left, right)
```
In this example, the merge function merges the Left and Right sublists.

```/* Double-Click To Select Code */

function merge(left, right)
var list result
while length(left) > 0 or length(right) > 0
if length(left) > 0 and length(right) > 0
if first(left) <= first(right)
append first(left) to result
left = rest(left)
else
append first(right) to result
right = rest(right)
else if length(left) > 0
append first(left) to result
left = rest(left)
else if length(right) > 0
append first(right) to result
right = rest(right)
end while
return result
```

## Here is the C Code for Merge Sort:

```/* Double-Click To Select Code */

#include <stdio.h>
#include<conio.h>

void mergesort(int arr[], int l, int h);

void main(void)
{
int array,n,i = 0;
clrscr();
printf("Enter the number of elements to be sorted: ");
scanf("%d",&n);
printf("\nEnter the elements to be sorted: \n");
for(i = 0 ; i < n ; i++ )
{
printf("\tArray[%d] = ",i);
scanf("%d",&array[i]);
}

printf("\nBefore Mergesort:");  //Array Before Mergesort
for(i = 0; i < n; i++)
{
printf("%4d", array[i]);
}
printf("\n");

mergesort(array, 0, n - 1);

printf("\nAfter Mergesort:");  //Array After Mergesort
for(i = 0; i < n; i++)
{
printf("%4d", array[i]);
}
printf("\n");
getch();
}

void mergesort(int arr[], int l, int h)
{
int i = 0;
int length = h - l + 1;
int pivot  = 0;
int merge1 = 0;
int merge2 = 0;
int temp;

if(l == h)
return;

pivot  = (l + h) / 2;

mergesort(arr, l, pivot);
mergesort(arr, pivot + 1, h);

for(i = 0; i < length; i++)
{
temp[i] = arr[l + i];
}

merge1 = 0;
merge2 = pivot - l + 1;

for(i = 0; i < length; i++)
{
if(merge2 <= h - l)
{
if(merge1 <= pivot - l)
{
if(temp[merge1] > temp[merge2])
{
arr[i + l] = temp[merge2++];
}

else
{
arr[i + l] = temp[merge1++];
}
}

else
{
arr[i + l] = temp[merge2++];
}
}

else
{
arr[i + l] = temp[merge1++];
}
}
}
```

### Output of Program:

Please Comment If You Liked This Post !!