DAA- Merge Sort

Merge Sort

Merge sort is an algorithm that is similar to the quick sort algorithm. It is because both of them use the divide and conquer approach to sort the elements of the list. It is one of the most popular and efficient algorithms for sorting. It first divides the given list into two equal halves. Later, it calls itself for the two equal halves and then merges the two halves that are sorted. To perform the merging, we need to define the merge() function.

The sub-lists are again divided into halves and this process continues until the list cannot be divided further. We then combine the pair of one-element lists to convert them into two-element lists and thereby sorting them in the process. Later, the sorted two-element pairs are merged into the four-element lists. This goes on until we get a sorted list.

Algorithm for Merge sort.

MERGE_SORT(array, begin, end)    
if begin < end  
set mid = (begin + end)/2  
MERGE_SORT(array, begin, mid)  
MERGE_SORT(array, mid + 1, end)  
MERGE (array, begin, mid, end)  
end of if  
END MERGE_SORT

The MERGE function is an important part of this algorithm as it merges the two sorted sub-arrays A[begin…mid] and A[mid+1…end]. This would build one sorted array A[begin…end].

How does Merge sort Algorithm work?

Now, let’s look into the working of the merge sort Algorithm with an example.

Let us consider the elements of the array are –

According to the merge sort, we first divide the given list/array into two equal halves. We then continue dividing the list into equal parts until it cannot be divided further.

The given array consists of eight elements, so it is divided into two subarrays with 4 elements in each.

Then we again divide these two arrays into halves. As they are of size 4, we divide them into subarrays of size 2.

Now, we divide these arrays and reach a point where it cannot be further divided.

Now, combine them in the same manner as they were divided.

Whil combining, we first compare the element of each array and then combine them into another array in a sorted order.

So, we first compare 12 and 31, as both are in sorted positions we move to next. Now we compare 25 and 8, sort them, and put 8 first followed by 25. We then compare 32 and 17, as they are unsorted, we sort them, and put 17 first followed by 32. After that, compare 40 and 42, and place them in a sequential order.

In the next iteration of combining the arrays, we compare the arrays with two data values and merge them into an array of found values in a sorted order.

Now, we have reached to the final merging of the arrays. After merging of the above two arrays, the array would look like –

Finally, we get a completely sorted array.

Merge sort complexity

Now, let us see the time and space complexity of merge sort in various cases such as the best case, average case, and worst case.

1. Time Complexity

Best Case Complexity – The best case occurs when there is no sorting required, i.e. when the given array itself is sorted. The best-case time complexity of merge sort would be O(n*log n).

Average Case Complexity – This case will occur when the elements of array are in a jumbled order, Which means that the elements are neither properly ascending nor properly descending. The time complexity of merge sort for average case is O(n*log n).

Worst Case Complexity – The worst case occurs when the array elements are required to be sorted in the reverse order. That means suppose you have to sort the array elements in ascending order, but its elements in the array are in a descending order. The complexity in this case would be O(n*log n).

2. Space Complexity

The space complexity of merge sort is O(n). It is because we require an extra variable for swapping in merge sort.

Implementation of merge sort

#include <stdio.h>  
void Merge(int arr[], int begin, int mid, int end)    
{    
    int x, y, k;  
    int n1 = mid - begin + 1;    
    int n2 = end - mid;    
    int LeftArray[n1], RightArray[n2]; 
    for (x = 0; x < n1; x++) {  
    LeftArray[x] = arr[begin + x];    
    }
    for (y = 0; y < n2; y++)  {  
    RightArray[y] = arr[mid + 1 + y];    
    }   
    x = 0; 
    y = 0; 
    k = begin;  
      
    while ((x < n1) && (y < n2))    
    {    
        if(LeftArray[x] <= RightArray[y])    
        {    
            arr[k] = LeftArray[x];    
            x++;    
        }    
        else    
        {    
            arr[k] = RightArray[y];    
            y++;    
        }    
        k++;    
    }    
    while (x<n1)    
    {    
        arr[k] = LeftArray[x];    
        x++;    
        k++;    
    }    
      
    while (y<n2)    
    {    
        arr[k] = RightArray[y];    
        y++;    
        k++;    
    }    
}    
  
void mergeSort(int arr[], int begin, int end)  
{  
    if (begin < end)   
    {  
        int mid = (begin + end) / 2;  
        mergeSort(arr, begin, mid);  
        mergeSort(arr, mid + 1, end);  
        Merge(arr, begin, mid, end);  
    }  
}  
  
void printArray(int arr[], int n)  
{    
    for (int x = 0; x < n; x++)  
        printf("%d ", arr[x]);  
    printf("\n");  
}  
  
int main()  
{  
    int arr[] = { 12, 31, 25, 8, 32, 17, 40, 42 };  
    int n = sizeof(arr) / sizeof(arr[0]);  
    printf("Before sorting array elements are - \n");  
    printArray(arr, n);  
    mergeSort(arr, 0, n - 1);  
    printf("After sorting array elements are - \n");  
    printArray(arr, n);  
    return 0;  
}