Merge sort is based on the divide conquer strategy. Array is divided in to two halves.if the array length is n, then it is divided into n/2,n/4,n/8…. and each part is sorted independently, then conquered into the sorted array.
The efficiency of merge sort is O(n log n)
C Program
#include <stdio.h> #include <stdlib.h> #define MAX_ARY 10 void merge_sort(int x[], int end, int start); int main(void) { int ary[MAX_ARY]; int j = 0; printf("\n\nEnter the elements to be sorted: \n"); for (j=0;j<MAX_ARY;j++) scanf("%d",&ary[j]); /* array before mergesort */ printf("Before :"); for (j = 0; j < MAX_ARY; j++) printf(" %d", ary[j]); printf("\n"); merge_sort(ary, 0, MAX_ARY - 1); /* array after mergesort */ printf("After Merge Sort :"); for (j = 0; j < MAX_ARY; j++) printf(" %d", ary[j]); printf("\n"); getch(); } /* Method to implement Merge Sort*/ void merge_sort(int x[], int end, int start) { int j = 0; const int size = start - end + 1; int mid = 0; int mrg1 = 0; int mrg2 = 0; int executing[MAX_ARY]; if(end == start) return; mid = (end + start) / 2; merge_sort(x, end, mid); merge_sort(x, mid + 1, start); for (j = 0; j < size; j++) executing[j] = x[end + j]; mrg1 = 0; mrg2 = mid - end + 1; for (j = 0; j < size; j++) { if(mrg2 <= start - end) if(mrg1 <= mid - end) if(executing[mrg1] > executing[mrg2]) x[j + end] = executing[mrg2++]; else x[j + end] = executing[mrg1++]; else x[j + end] = executing[mrg2++]; else x[j + end] = executing[mrg1++]; } }