Competitive Programming - Crack Your Coding Interview, C++/

...

/

Merge Sort

Merge Sort

Use Recursion to implement merge sort.

We'll cover the following...

Problem statement

The problem is the same as in the Bubble Sort lesson. We are given an input array of numbers and we need to sort them. The only difference will be in the time complexity, which we will discuss later.

Solution

Suppose we had to sort an array A. A subproblem would be to sort a subsection of this array starting at index p and ending at index r, denoted as A[p…r].

  • Divide — If q is the half-way point between p and r, we can split the subarray A[p…r] into two arrays A[p…q] and A[q+1, r].

  • Conquer — In the conquer step, we try to sort both the subarrays A[p…q] and A[q+1, r]. If we haven’t yet reached the base case, we again divide both these subarrays and try to sort them.

  • Combine — When the conquer step reaches the base step and we get two sorted subarrays A[p…q] and A[q+1, r] for array A[p…r], we combine the results by creating a sorted array A[p…r] from two sorted subarrays A[p…q] and A[q+1, r].

Let us visualize this to understand these operations better.

Now that the technique is clear, let’s move on to the implementation and then see the time complexity of this sorting technique.

Press + to interact
#include <iostream>
using namespace std;
void Merge(int *a, int s, int e){
    int mid=(s+e)/2;
    int i=s;
    int j = mid + 1;
    int k = s;
    int temp[100];
    while(i<=mid && j<=e){
        if(a[i]<a[j]){
            temp[k++] = a[i++];
        }
        else{
            temp[k++] = a[j++];
        }
    }
    while(i<=mid){
        temp[k++] = a[i++];
    }
    while(j<=e){
        temp[k++] = a[j++];
    }
    for(int i=s;i<=e; i++){
        a[i] = temp[i];
    }
}
void MergeSort(int a[],int s, int e){
    if(s>=e){
        return;
    }
    int mid=(s+e)/2;
    MergeSort(a,s,mid);
    MergeSort(a,mid+1,e);
    Merge(a,s,e);
}
int main() {
    int arr[] = {1,9,4,6,13,74,56,32,41,7,5};
    MergeSort(arr,0,9);
    for(int i=0; i<10; i++)
        cout<<arr[i]<<" ";
    return 0;
}

Explanation:

  • On line 4, we define our Merge() function, which will perform the merging after the array is subdivided into
...