# Merge Sort

Sorting Algorithm

Share

In this tutorial we will learn about Merge sort algorithm.

In this sorting algorithm we use the idea of divide and conquer. We divide the array into two parts, sort them and then merge them to get the elements in ascending or descending order.

Merge sorting is done recursively. We take an array and keep dividing from the middle till we get only one element in each halves (sub-array).

Then we sort the sub-arrays and merge them back to get the final sorted array.

## Algorithm

``````/**
* a[0:n-1] is an array of n elements.
*/
MergeSort(a, beg, end)
Begin
if beg < end then
Set mid = (beg+end)/2;
Call MergeSort(a, beg, mid);
Call MergeSort(a, mid+1, end);
Call MergeSortedArray(a, beg, mid, mid+1, end);
endif
End
``````

## Code in C

``````#include <stdio.h>
#define SIZE 6  //array size

//function declaration
void mergeSort(int *a, int beg, int end);
void mergeSortedArray(int *a, int lbeg, int lend, int rbeg, int rend);  //l = left sub array and r = right sub array

int main(){
int a[SIZE] = {5,4,3,1,2,6};  //array to sort in  ascending order
int i;
mergeSort(a, 0, SIZE-1);  //beg = 0 and end = 5
for(i = 0; i < SIZE; i++){
printf("%d\t", a[i]);
}
return 0;
}

void mergeSort(int *a, int beg, int end){
int mid;
if(beg < end){
mid = (beg+end)/2;
mergeSort(a, beg, mid);
mergeSort(a, mid+1, end);
mergeSortedArray(a, beg, mid, mid+1, end);
}
}

void mergeSortedArray(int *a, int lbeg, int lend, int rbeg, int rend){
int pa = lbeg, pb = rbeg, pt = lbeg, tmp[SIZE];
while(pa <= lend && pb <= rend){
if(a[pa] < a[pb]){
tmp[pt++] = a[pa++];
}else{
tmp[pt++] = a[pb++];
}
}
if(pa > lend){
while(pb <= rend){  //left sub array exhausted
tmp[pt++] = a[pb++];
}
}else{
while(pa <= lend){  //right sub array exhausted
tmp[pt++] = a[pa++];
}
}

//write sorted element in array a
for(pt = lbeg; pt <= rend; pt++){
a[pt] = tmp[pt];
}
}
``````

## Time Complexity

For an array of n elements order of Merge Sort is O(nlog2n)

Share