Merge Sort

Sorting an arrary using Merge Sort.

Merge Sort is a sorting algorithm based on the divide and conquer strategy. Merge Sort splits the array into two equal halves (sub-arrays) and continues doing so recursively. The splitting continues till a sub-array is reduced to a single element, after which merging begins. During merge operation, the sub-arrays are merged in sorted order into an auxiliary array.

This algorithm was invented by Hungarian-American mathematician 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 recursion 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 the 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.


Java Program to sort numbers using Merge Sort. Implemented in Java 11


Python Program to sort numbers using Merge Sort.

C++ Program to sort numbers using Merge Sort.


using namespace std;

vector<int> auxvec;

// Function to merge the sorted sub-arrays into a bigger array.
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];

// MergeSort function splits each sub-array till only a single element is available in the sub-array 
// and then proceeds with the merge of the sub-arrays into a bigger auxiliary array.
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
    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

Copyright (c) 2019-2021,
All rights reserved.