Algotree > Algorithms > Sorting Algorithms > Merge Sort

Merge Sort

Sorting an arrary using Merge Sort.

Merge Sort is a sorting algorithm based on divide and conquer strategy. This algorithm was invented by John von Neumann.
The Merge Sort algorithm is as follows

Algorithm : Merge Sort

1. Split the array all the way down until each sub-array contains a single element. The splitting operation makes use of recursion and continues as recurssion progresses.
2. Merge the sub-arrays into a bigger sorted sub-array using additional space. The merging operation happens during the way out of the recursion stack and requires an auxiliary array for merging.

Example of Merge Sort

Time complexity of Merge Sort : O(n.log(n)). The time complexity of merging two sorted sub-arrays each of length n is 2n. Since merging happens at each level during way out, the time complexity is O(n)*(number of levels) i.e log(n). Thus the complexity of merge sort is O(n.log(n)) \

Space complexity of Merge Sort : O(n) as an auxiliary array is needed for mergeing the sub-arrays.

C++14 : Merge Sort implementation

#include<iostream>
#include<vector>

using namespace std;

vector<int> auxvec;

void Merge (vector<int>& vec, int low, int mid, int high) {

    int left_index = low;
    int right_index = mid+1;
    int aux_index = low;

    /* Merge elements from vec[low : mid] and vec[mid+1 : high]
                                ^                  ^
                                |                  |
                              left_index       right_index    */

    // Pick the smaller number between the left part and the right part
    while (left_index <= mid and right_index <= high) {
       if (vec[left_index] <= vec[right_index]) {
          auxvec[aux_index++] = vec[left_index++];
       } else {
          auxvec[aux_index++] = vec[right_index++];
       }
    }

    if (left_index <= mid) {
       // There are still some unpicked numbers in the left part
       for (int i = left_index; i <= mid; i++) {
           auxvec[aux_index++] = vec[i];
       }
    } else {
       // There are still some unpicked numbers in the right part
       for (int i = right_index; i <= high; i++) {
           auxvec[aux_index++] = vec[i];
       }
    }

    // Copy numbers from the sorted auxillary vector into the original vector
    for (int i=low; i<=high; i++) {
        vec[i] = auxvec[i];
    }
}

void MergeSort (vector<int>& vec, int low, int high) {

    int mid;
    if (low < high) {
       mid = (low + high)/2;
       MergeSort (vec, low, mid); // Recursively splits left half of the array
       MergeSort (vec, mid+1, high); // Recursively splits right half of the array
       Merge (vec, low, mid, high); // Merge left and right half of the array keeping it sorted.
    }
}

int main(){

    vector<int> vec = {7, 3, 5, 2, 4, 1, 8, 6};
    // Allocate space for the auxillary vector
    auxvec.resize(vec.size());
    MergeSort (vec, 0, vec.size()-1);

    cout << "Sorted numbers : ";
    for(auto& it: vec)
        cout << it << " ";
    return 0;
}

Output of Merge Sort

Sorted numbers : 1 2 3 4 5 6 7 8