Merge Sort | Sorting Techniques in Data Structure

Merge Sort - 

-> Merge sort is a sorting technique based on divide and conquer technique. With worst-case time complexity being Ο(n log n), it is one of the most respected algorithms.

-> Merge sort first divides the array into equal halves and then combines them in a sorted manner.

-> In Merge Sort, the given unsorted array with n elements, is divided into n subarrays, each having one element, because a single element is always sorted in itself. Then, it repeatedly merges these subarrays, to produce new sorted subarrays, and in the end, one complete sorted array is produced.



-> The concept of Divide and Conquer involves three steps:

1. Divide the problem into multiple small problems.

2. Conquer the subproblems by solving them. The idea is to break down the problem into atomic subproblems, where they are actually solved.


3. Combine the solutions of the subproblems to find the solution of the actual problem.


Let's take an example, Divide and Rule -

When Britishers came to India, they saw a country with different religions living in harmony, hard working but naive citizens, unity in diversity, and found it difficult to establish their empire. So, they adopted the policy of Divide and Rule. Where the population of India was collectively a one big problem for them, they divided the problem into smaller problems, by instigating rivalries between local kings, making them stand against each other, and this worked very well for them.


Well that was history, and a socio-political policy (Divide and Rule), but the idea here is, if we can somehow divide a problem into smaller sub-problems, it becomes easier to eventually solve the whole problem.

/* C Program to implement merge sort */

#include<stdio.h>
void merge(int a[], int low, int mid, int high)
{
    int b[100];
    int i = low, j = mid + 1, k = 0;
    while (i <= mid && j <= high) 
{
        if (a[i] <= a[j])
            b[k++] = a[i++];
        else
            b[k++] = a[j++];
    }
    while (i <= mid)
        b[k++] = a[i++];
  
    while (j <= high)
        b[k++] = a[j++];
    k--;
    while (k >= 0) {
        a[low + k] = b[k];
        k--;
    }
}
void mergesort(int a[], int low, int high)
{
    if (low < high) {
        int m = (high + low)/2;
        mergesort(a, low, m);
        mergesort(a, m + 1, high);
        merge(a, low, m, high);
    }
}
int main()
{
int a[100], i,n;
printf("Enter n value:");
scanf("%d", &n);
for(i=0;i<n;i++)
   scanf("%d",&a[i]);
mergesort(a,0,n-1);
printf("Sorted array is:\n"); 
for(i=0;i<n;i++)
   printf("%d  ",a[i]);
return 0;   
}

OUTPUT:

Enter n value:5
4 75 74 2 54
Sorted array is:
2  4  54  74  75