Merge Sort

Sorting, Divide and Conquer, Recursion, Arrays

Problem Statement:
Given an array with N elements. Sort the array in ascending order using Merge Sort Algorithm.

Why Merge Sort?
Merge sort is one of the best time-efficient algorithms to sort an array in O(n log n) time and O(n) space complexity.

It works on single smallest truth — if there is only one element in the array, it’s already considered as sorted. Based on this, we use divide and conquer technique to reduce the sorting problem into smaller sub problems and merge it to whole single sorted array.

As, we can see it divides the given array repeatedly. I’m getting an intuition to solve the problem with the help of Recursion :)

Approach:
Let’s divide the problem into two parts:

1. Divide repeatedly until we reach single element in the array
2. Merge the divided arrays in sorted order.

Speaking of dividing the array, we don’t want to create new two arrays to divide the single array. we can take advantage of using indexes to partition the array into smaller chunks.

Image Credit: Coding Ninjas

Divide arrays into smaller chunks:

Let’s take two pointers, low and high. low will point to start of the chunk and high will point to end of the chunk. We’ll find the middle of the chunk by adding low and high, then dividing it by 2. This will happen repeatedly divide the chunks into smaller chunks until there is only one element in the array.

For stopping the recursion, we need to define a base case. Here, the base case is to stop once low and high point to same index.

Pseudo Code:

mergeSort(array, low, high)
  // base_case
  if(low == high)
      return 

  low = 0, high = N
  middle = (low + high) / 2
  mergeSort(array, low, middle)
  mergeSort(array, middle + 1, high)
  merge(array, low, middle, high)

Once the base case is true, we’ll break the recursive call and move to next. When both the recursive call stops, merging those two chunks will happen.

Merging two sorted arrays:

Now the array is divided into two smaller chunks based on indexes. Since, both the array is sorted, we can use a single loop with two pointers and a temp array to merge them both into one sorted array. We’ve to do this process repeatedly to sort the whole given array.

The entire elements in the two smaller chunks is pushed to temporary array. Now, we have to replace the element in positions of the current chunk to sorted elements.

Pseudo Code:

merge(arr, low, mid, high):
  vector<int> temp
  int left = low, right = mid + 1
  
  // fill the temp array with arr element in sorted order
  while left <= mid and right <= high:
    if arr[left] <= arr[right]:
      temp.push_back(arr[left])
      left++
    else:
      temp.push_back(arr[right])
      right++
  
  // pushing left-out elements in first chunk
  while left <= mid:
    temp.push_back(arr[left]

  // pushing left-out elements in second chunk
  while right <= high:
    temp.push_back(arr[right])

  // replace arr elements in sorted order 
  for(int k = low; k <= high; k++)
        arr[k] = temp[k - low] 

  // since the offset is low, 
  // we have to subtract it from K to point to correct index of temp

Once the merge is done, we can confirm that the chunk is arranged in sorted order. This process is executed repeatedly, when we have two arrays to merge.

Entire Code:

void merge(vector<int>& arr, int low, int md, int high){
    vector<int> temp;
    int left = low, right = md + 1;

    while(left <= md and right <= high){
        if(arr[left] <= arr[right]){
            temp.push_back(arr[left]);
            left++;
        }else{
            temp.push_back(arr[right]);
            right++;
        }
    }
    
    while(left <= md){
        temp.push_back(arr[left]);
        left++;
    }

    while(right <= high){
        temp.push_back(arr[right]);
        right++;
    }

    for(int k = low; k <= high; k++){
        arr[k] = temp[k - low];
    }

}

void sort(vector<int>& arr, int low, int high){
    if(low == high) return;

    int md = (low + high) / 2;

    sort(arr, low, md);
    sort(arr, md + 1, high);
    merge(arr, low, md, high);
}

void mergeSort(vector < int > & arr, int n) {
    sort(arr, 0, n-1);
}

Time Complexity:
N(log(N)) — where N is number of elements in the array. Dividing array into smaller chunks require log(N) time and it’s multiplied by N, since, we are merging those two smaller chunks.

Space Complexity:
O(N) — where N is elements in the array. temp array used to hold the merged elements of the array.