Merge Sort

 Merge Sort Algorithm

Problem:  Given an array of size n, sort the array using Merge Sort.

Example 1:

Input: N=5, ar[]={4,2,1,63,70}

Output: 1,2,4,63,70

Example 2:

Input: N=7,ar[]={3,2,80,5,1,40,2}

Output: 1,2,3,5,40,80

Solution

Disclaimer: Don't jump directly to the solution, try it out yourself first.

Intuition:

1. Merge Sort is an algorithm based on the divide-and-conquer strategy. It splits the given array into smaller segments and then combines the sorted segments back together.
2. There are two key functions:

• merge(): This function is responsible for combining two halves of the array. It takes into account that both sections are already sorted and merges them into a single sorted array.
• mergeSort(): This function breaks the array down into two parts, specifically from low to mid and from mid + 1 to high.

1.  low = leftmost index of the array
2.  high = rightmost index of the array
3.  mid = Middle index of the array 

• We recursively split the array, and go from top-down until all sub-arrays size becomes 1.

Approach:

We will implement two functions: mergeSort() and merge().

1. mergeSort(arr[], low, high):

• To carry out merge sort, we begin by dividing the array into two halves. Notably, we don't need to create separate arrays; instead, we can work with the indices(index) that represent the current range. For instance, if the initial range of the array is from 0 to 4 (using 0-based indexing), we can find the middle index using the formula (0 + 4) / 2 = 2. This results in the left half ranging from 0 to 2 and the right half from 3 to 4.When dealing with a general range from low to high, the two halves will be defined as low to mid and mid + 1 to high, where mid = low +( high-low) / 2. This division process continues until the range size is reduced sufficiently.

• In mergeSort(), we recursively divide the array around the middle index instead of creating new arrays by making the following recursive calls:

1. mergeSort(arr, low, mid) [Left half of the array]
2. mergeSort(arr, mid + 1, high) [Right half of the array]
3. Here, low represents the leftmost index, high represents the rightmost index, and mid denotes the middle index of the array.

• To complete the recursive function, we must establish a base case. As determined earlier, the recursion halts when the range has only one element left, meaning that the leftmost index low equals the rightmost index high.Base Case: If (low >= high), return.

Pseudocode:

merge(arr[], low, mid, high):

In the merge function, we will create a temporary array to hold the elements from the two sorted halves after merging.

• The left half of the array spans from low to mid, while the right half ranges from mid + 1 to high.

• We will initialize two pointers:

• left starting at low
• right starting at mid + 1
• Using a while loop (while(left <= mid && right <= high)), we will compare elements from both halves:

• Select the smaller of the two elements pointed to by left and right.
• Insert the smaller element into the temporary array.
• Once one half is exhausted, any remaining elements from the other half will be copied directly into the temporary array.

• Finally, we will transfer the elements from the temporary array back to the original array, specifically from index low to high.

The pseudocode will look like this:

Code

void merge(std::vector& arr, int low, int mid, int high) {
    // Create a temporary array to hold the merged elements
    std::vector temp(high - low + 1);
    
    int left = low;          // Initialize left pointer
    int right = mid + 1;    // Initialize right pointer
    int index = 0;          // Index for temp array

    // Merge the two halves
    while (left <= mid && right <= high) {
        if (arr[left] <= arr[right]) {
            temp[index++] = arr[left++]; // Insert from left half
        } else {
            temp[index++] = arr[right++]; // Insert from right half
        }
    }

    // Copy remaining elements from the left half, if any
    while (left <= mid) {
        temp[index++] = arr[left++];
    }

    // Copy remaining elements from the right half, if any
    while (right <= high) {
        temp[index++] = arr[right++];
    }

    // Transfer elements from temp back to the original array
    for (int i = 0; i < temp.size(); i++) {
        arr[low + i] = temp[i];
    }
} 

Example

Given:

arr={9,4,7,6,3,1,5};

Code

#include<bits/stdc++.h>
using namespace std;

void merge(vector &arr, int low, int mid, int high) {
    vector temp; // temporary array
    int left = low;      // starting index of left half of arr
    int right = mid + 1;   // starting index of right half of arr

    //storing elements in the temporary array in a sorted manner//

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

    // if elements on the left half are still left //

    while (left <= mid) {
        temp.push_back(arr[left]);
        left++;
    }

    //  if elements on the right half are still left //
    while (right <= high) {
        temp.push_back(arr[right]);
        right++;
    }

    // transfering all elements from temporary to arr //
    for (int i = low; i <= high; i++) {
        arr[i] = temp[i - low];
    }
}

void mergeSort(vector &arr, int low, int high) {
    if (low >= high) return;
    int mid = (low + high) / 2 ;
    mergeSort(arr, low, mid);  // left half
    mergeSort(arr, mid + 1, high); // right half
    merge(arr, low, mid, high);  // merging sorted halves
}

int main() {

    vector arr = {9, 4, 7, 6, 3, 1, 5}  ;
    int n = 7;

    cout << "Before Sorting Array: " << endl;
    for (int i = 0; i < n; i++) {
        cout << arr[i] << " "  ;
    }
    cout << endl;
    mergeSort(arr, 0, n - 1);
    cout << "After Sorting Array: " << endl;
    for (int i = 0; i < n; i++) {
        cout << arr[i] << " "  ;
    }
    cout << endl;
    return 0 ;
}

Output

Before Sorting Array:
9 4 7 6 3 1 5
After Sorting Array:
1 3 4 5 6 7 9

Time complexity: O(nlogn) 

Reason: At each step, we divide the whole array, for that logn and we assume n steps are taken to get sorted array, so overall time complexity will be nlogn

Space complexity: O(n)  

Reason: We are using a temporary array to store elements in sorted order.

Auxiliary Space Complexity: O(n)