🚀 Programming Example
Merge Sort program in the data structure
Below we have a C program implementing merge sort algorithm.
/*
a[] is the array, p is starting index, that is 0,
and r is the last index of array.
*/
#include <stdio.h>
// lets take a[5] = {32, 45, 67, 2, 7} as the array to be sorted.
// merge sort function
void mergeSort(int a[], int p, int r)
{
int q;
if(p < r)
{
q = (p + r) / 2;
mergeSort(a, p, q);
mergeSort(a, q+1, r);
merge(a, p, q, r);
}
}
// function to merge the subarrays
void merge(int a[], int p, int q, int r)
{
int b[5]; //same size of a[]
int i, j, k;
k = 0;
i = p;
j = q + 1;
while(i <= q && j <= r)
{
if(a[i] < a[j])
{
b[k++] = a[i++]; // same as b[k]=a[i]; k++; i++;
}
else
{
b[k++] = a[j++];
}
}
while(i <= q)
{
b[k++] = a[i++];
}
while(j <= r)
{
b[k++] = a[j++];
}
for(i=r; i >= p; i--)
{
a[i] = b[--k]; // copying back the sorted list to a[]
}
}
// function to print the array
void printArray(int a[], int size)
{
int i;
for (i=0; i < size; i++)
{
printf("%d ", a[i]);
}
printf("\n");
}
int main()
{
int arr[] = {32, 45, 67, 2, 7};
int len = sizeof(arr)/sizeof(arr[0]);
printf("Given array: \n");
printArray(arr, len);
// calling merge sort
mergeSort(arr, 0, len - 1);
printf("\nSorted array: \n");
printArray(arr, len);
return 0;
}
Given array:
32 45 67 2 7
Sorted array:
2 7 32 45 67
Merge Sort follows the rule of Divide and Conquer to sort a given set of numbers/elements, recursively, hence consuming less time.
In the last two tutorials, we learned about Selection Sort and Insertion Sort, both of which have a worst-case running time of O(n2). As the size of input grows, insertion and selection sort can take a long time to run.
Merge sort , on the other hand, runs in O(n*log n) time in all the cases.
Before jumping on to, how merge sort works and it's implementation, first lets understand what is the rule of Divide and Conquer?
First understand the algorithm carefully. Then study the program line-by-line and compare it with the output. Finally, review the explanation section to strengthen your logic and programming understanding.
Rewrite the program without looking at the code. Modify values, conditions or logic and run it again. This helps improve confidence and strengthens coding skills much faster.