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 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