Merge Sort is a well-known and effective sorting method that divides a problem into numerous smaller problems using the divide and conquer technique. It divides the supplied array into two more equal halves until the size of succeeding halves equals 1, at which point it makes calls for the two halves and joins the two sorted halves.

Implementation of merge sort

1. #include <stdio.h>
2. /* Function to merge the subarrays of a[] */
3. void merge(int a[], int beg, int mid, int end)
4. {
5. int i, j, k;
6. int n1 = mid – beg + 1;
7. int n2 = end – mid;
8. int LeftArray[n1], RightArray[n2]; //temporary arrays.