The ones who are crazy enough to think they can change the world are the ones who do.
- Steve Jobs

Merge Sort

Merge sort algorithm uses the technique of divide, conquer and combine.

Divide

Divide the elements in an array into two sub-array of n/2 elements of each sub-arrays.

Conquer

Sorting the two sub-arrays recursively using merge sort.

Combine

Merging the two sorted sub-arrays of size n/2 to produce the sorted arrays of n elements.

Advantages - Merge Sort

  • Merge sort algorithm is best case for sorting slow-access data e.g) tape drive.
  • Merge sort algorithm is better at handling sequential - accessed lists.

Disadvantages - Merge Sort

  • The running time of merge sort algorithm is 0(n log n). which turns out to be the worse case.
  • Merge sort algorithm requires additional memory spance of 0(n) for the temporary array TEMP.

C program - Merge Sort

Here is the program to demonstrate Merge Sort.

merge-sort.c
#include <stdio.h>
void merge(int a[], int, int, int);
void merge_sort(int a[], int, int);
int main()
{
int arry[10],i,n;
printf("\n Enter the size of the array : ");
scanf("%d",&n);
printf("\n Enter %d elements in the array : \n",n);
for(i=0; i<n; i++)
scanf("%d", &arry[i]);
merge_sort(arry, 0, n-1);
printf("\n Sorted Array in ascending order is : \n");
for(i=0; i<n; i++)
printf("%d ",arry[i]);
return 0;
}
void merge(int arry[], int beg, int mid, int end)
{
int i = beg, j = mid + 1, index = beg, temp[10], k;
while((i <= mid) && (j <= end))
{
if(arry[i] < arry[j])
{
temp[index] = arry[i];
i++;
}
else
{
temp[index] = arry[j];
j++;
}
index++;
}
if(i > mid)
{
while(j <= end)
{
temp[index] = arry[j];
j++;
index++;
}
}
else
{
while(i <= mid)
{
temp[index]= arry[i];
i++;
index++;
}
}
for(k = beg;k < index; k++)
arry[k] = temp[k];
}
void merge_sort(int arry[], int beg, int end)
{
int mid;
if(beg < end)
{
mid = (beg + end) / 2;
merge_sort(arry, beg, mid);
merge_sort(arry, mid+1, end);
merge(arry, beg, mid, end);
}
}
Enter the size of the array : 5 
Enter 5 elements in the array :
4 3 1 2 5 
Sorted Array in ascending order is : 
1 2 3 4 5

Report Us

We may make mistakes(spelling, program bug, typing mistake and etc.), So we have this container to collect mistakes. We highly respect your findings.

Report