Algotree > Algorithms > Sorting Algorithms > Merge Sort

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.

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.

array : to be sorted. Example : [ 7, 3, 5, 2, 4, 1, 8, 6 ]
low : index of the first element i.e 0
high : index of the last element i.e length / size of array - 1 i.e 7

MergeSort ( array, low, high )

1.  If ( low < high ) then
2.      mid = ( low + high ) / 2
3.      Recursively split the left half : MergeSort ( array, low, mid )
4.      Recursively split the right half : MergeSort ( array, mid + 1, high )
5.      Merge ( array, low, mid, high )

Steps showing the recursive splitting of the left sub-array

Step / Call	Array	High	Check ( low < high )	Mid
1. MergeSort ( array, low, high )	[ 7, 3, 5, 2, 4, 1, 8, 6 ]	7	Yes	3
2. MergeSort ( array, low, mid )	[ 7, 3, 5, 2, 4, 1, 8, 6 ]	3	Yes	1
3. MergeSort ( array, low, mid )	[ 7, 3, 5, 2, 4, 1, 8, 6 ]	1	Yes	0
4. MergeSort ( array, low, mid )	[ 7, 3, 5, 2, 4, 1, 8, 6 ]	0	No	-

Since low is not less than high, the recursive splitting of the left sub-array ends and the function returns
to call the next instruction i.e MergeSort ( array, mid + 1, high )

Steps showing the recursive splitting of the right sub-array of the call stack

Step / Call	Array	Low	High	Check ( low < high )	Mid
1. MergeSort ( array, mid + 1, high )	[ 7, 3, 5, 2, 4, 1, 8, 6 ]	1	1	No	-

Since low is not less than high, the recursive splitting of the right sub-array ends and the function returns
to call the next instruction i.e Merge ( array, low, mid, high )

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 additional array for merging.

Merge ( array, low, mid, high )
1.   While the left sub-array i.e array [ low : mid ] and the right sub-array i.e [ mid + 1 : high ] are not empty. do
2.       Pick the smaller number at the front of either of the two sub-arrays and place this number in the auxiliary array.
3.   If there are still numbers left in the left sub-array, then add them to the auxiliary array.
4.   If there are still numbers left in the right sub-array, then add them to the auxiliary array.
5.   Copy the ( sorted ) numbers from the auxiliary array back to the original array.

Steps showing the merge of the left sub-array and the right sub-array of the array

Step / Call	Array	Low	Mid	High
1. Merge ( array, low, mid, high )	[ 7, 3, 5, 2, 4, 1, 8, 6 ]	0	0	1

After the first call to Merge, the sub-array [ low : high ] i.e array [ 0 : 1 ] gets sorted and becomes [ 3, 7, 5, 2, 4, 1, 8, 6 ].

Example Merge Sort

Time complexity : 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 : O ( n ), as an auxiliary array is needed for merging the sub-arrays.

Merge Sort Implementation


# Function to merge the sorted sub-arrays into a bigger array.
def Merge (aux_array, array, low, mid, high):

    left_index = low
    right_index = mid+1
    aux_index = low

    # Merge elements from array[low : mid] and array[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 (array[left_index] <= array[right_index]):
            aux_array[aux_index] = array[left_index]
            aux_index += 1
            left_index += 1
        else:
            aux_array[aux_index] = array[right_index]
            aux_index += 1
            right_index += 1

    if (left_index <= mid):
        # There are still some unpicked numbers in the left part
        for i in range(left_index, mid+1):
            aux_array[aux_index] = array[i]
            aux_index += 1
    else:
        # There are still some unpicked numbers in the right part
        for i in range(right_index, high+1):
            aux_array[aux_index] = array[i]
            aux_index += 1

    # Copy numbers from the sorted auxiliary array into the original array
    for i in range(low, high+1):
        array[i] = aux_array[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.
def MergeSort (aux_array, array, low, high):

    if (low < high):

       mid = int((low + high)/2)

       MergeSort (aux_array, array, low, mid)    # Recursively splits left half of the array
       MergeSort (aux_array, array, mid+1, high) # Recursively splits right half of the array

       Merge (aux_array, array, low, mid, high)  # Merge left and right half of the array keeping it sorted.

def main():

    array = [7, 3, 5, 2, 4, 1, 8, 6, 0, 10, 9]
    print("Unsorted array: " + str(array))

    # Allocate space for the auxiliary vector
    aux_array = [None] * len(array)

    MergeSort (aux_array, array, 0, len(array)-1)

    print("Sorted array using merge sort: "+ str(array))

if __name__ == "__main__" :
    main()

Output

Unsorted array: [7, 3, 5, 2, 4, 1, 8, 6, 0, 10, 9]
Sorted array using merge sort: [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

#include<iostream>
#include<vector>

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 auxiliary 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 auxiliary vector
    auxvec.resize(vec.size());
    MergeSort (vec, 0, vec.size()-1);

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

Output

Sorted numbers : 1 2 3 4 5 6 7 8

class Sort {

    private int aux_array[];

    // Allocate space to auxiliary array which is to be used for merging the sorted elements
    Sort (int sz) {
        aux_array = new int[sz];
    }

    // Function to merge the sorted sub-arrays into a bigger array.
    //void Merge (int[] aux_array, int[] array, int low, int mid, int high) {
    void Merge (int[] array, int low, int mid, int high) {

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

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

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

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

        // Copy numbers from the sorted auxiliary array into the original array
        for (int i=low; i<=high; i++) {
            array[i] = aux_array[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 (int[] aux_array, int[] array, int low, int high) {
    void MergeSort (int array[], int low, int high) {

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

    public static void main (String args[]) {

        int array[] = {7, 3, 5, 2, 4, 1, 8, 6};
        //int[] aux_array = new int[array.length];

        System.out.print("Unsorted array: ");

        for (int i=0; i<array.length; i++)
            System.out.print(array[i]+" ");
        System.out.println();

        Sort s = new Sort(array.length);
        s.MergeSort (array, 0, array.length-1);

        System.out.print("Sorted array using Merge-Sort: ");

        for (int i=0; i<array.length; i++)
            System.out.print(array[i]+" ");
    }
}

Output

Unsorted array: 7 3 5 2 4 1 8 6 
Sorted array using Merge-Sort: 1 2 3 4 5 6 7 8