Write a C Program to Implement the Merge Sort Algorithm

by

Aim:

To write a program in C to sorting the elements using Merge sort method.

Theory:

  • Like Quick Sort, Merge Sort is a Divide and Conquer algorithm.
  • It divides the input array into two halves, calls itself for the two halves and then merges the two sorted halves.
  • The merge () function is used for merging two halves. The merge(arr, l, m, r) is a key process that assumes that arr[l..m] And arr[m+1..r] are sorted and merges the two sorted sub-arrays into one.
  • Merge sort or Merge sort is an O (n log n) sorting algorithm.
  • It is easy to implement merge sort such that it is stable, meaning it preserves the input order of equal elements in the sorted output.
  • It is an example of the divide and conquers algorithmic paradigm. It is a comparison sort. The algorithm was invented by John von Neumann in 1945.
  • Merge sort recursively divides the array of elements into smaller sub-arrays and sort them and then merge these to form a complete sorted array. Conceptually, merge sort works as follows:
    • Divide the unsorted list into two sublists of about half the size
    • Divide each of the two sublists recursively until we have list sizes of length 1, in which case the list itself is returned
    • Merge the two sorted sublists back into one sorted list.

The program contains 2 important  functions:

  1. Merge () – This function takes as an argument the bounds of parts of the array to be merged. These two parts are contiguous and hence only 3 bounds are required. These parts are copied in separate arrays and then actual merging takes place. There are two pointers to the beginning of these arrays. The first elements are compared and smaller ones copied to the original array and its pointer incremented. This process continues till one of the arrays exhausts. After this, the remaining array is just copied. Thus the two arrays are merged and the result is a sorted array part.
  2. Merge sort () – This function breaks the array into two nearly equal parts and calls merge_sort for these parts. Then it calls the merge () function to merge these parts.

Algorithm:

  • Step 1 − if it is only one element in the list it is already sorted, return.
  • Step 2 − divide the list recursively into two halves until it can no more be divided.
  • Step 3 − merge the smaller lists into new list in sorted order.

Program:

#include <stdio.h>

#define size 100
void merge(int a[], int, int, int);
void merge_sort(int a[],int, int);
void main()
{
int arr[size], i, n;
printf("\n Enter the number of elements in the array : ");
scanf("%d", &n);
printf("\n Enter the elements of the array: ");
for(i=0;i<n;i++)
{
scanf("%d", &arr[i]);
}
merge_sort(arr, 0, n-1);
printf("\n The sorted array is: \n");
for(i=0;i<n;i++)
printf(" %d\t", arr[i]);

}
void merge(int arr[], int beg, int mid, int end)
{
int i=beg, j=mid+1, index=beg, temp[size], k;
while((i<=mid) && (j<=end))
{
if(arr[i] < arr[j])
{
temp[index] = arr[i];
i++;
}
else
{
temp[index] = arr[j];
j++;
}
index++;
}
if(i>mid)
{
while(j<=end)
{
temp[index] = arr[j];
j++;
index++;
}
}
else
{
while(i<=mid)
{
temp[index] = arr[i];
i++;
index++;
}
}
for(k=beg;k<index;k++)
arr[k] = temp[k];
}
void merge_sort(int arr[], int beg, int end)
{
int mid;
if(beg<end)
{
mid = (beg+end)/2;
merge_sort(arr, beg, mid);
merge_sort(arr, mid+1, end);
merge(arr, beg, mid, end);
}
}

Execution:

Input:
10 8 9 6 7 5 4 2 3 1 10

Output:

Enter the number of elements in the array: 
Enter the elements of the array: 
The sorted array is: 
1	 2	 3	 4	 5	 6	 7	 8	 9	 10

Result:

Thus, Implement of Merge Sort was executed successfully.

Leave a Comment