The Merge Sort algorithm belongs to the family of efficient sorting algorithms, whose average complexity is the best that we can find O(n log(n)).  It is an example of divide and conquer method. Through this method we are going to solve a problem recursively, applying three steps of recursion

  • Divide the problem into a number of small subproblems.
  • Conquer the subproblems by resolving them recursively.
  • Combine the solution of each subproblem into the solution for the original problem.

Review

Name Merge Sort
Best case O(log(n))
Average case O(log(n))
Worst case O(log(n))
Difficulty Medium
Family Efficient sorts

Algorithm

If the subproblem is large enough to solve recursively we call that recursive case, when there is no longer recursion we call it the base case. In particular:

(Base case) If the sequence length is between 0 and 1, it's ordered. 

(Divide) Else we divide the sequence into two half subsequence. If the number of elements is odd, one subsequence will have one more element.

(Conquer) Each of these sequences will be ordered, applying recursively the algorithm.

(Combine) Then the subsequence will be combined, in order to do that we take repeatedly the minimum and we put that into the output sequence, that will be ordered.

Merge Sort source

The algorithm was invented by John von Neumann in the year 1945.

How does it work

Let's consider an array A and divide it into n subarray (A1, A2,...An) until we obtain the An array with only one element.

We start with the array A

Array A

Then we split it into two subarrays: left subarray and right subarray

Array SplitWe go on splitting since the length of the subarray is greater than 1...

Subarray length

Now it's time to Merge!

We are going to merge recursively each subarray to produce a newly sorted subarray.

In this way, subarrays are merged to produce a longer sorted subarray until we reach the sorted array.

Merge procedure

At each step of Merge we:

  1. Compare the first element of the subarray A and the first element of subarray B.
  2. Select the smallest element
  3. Insert it into the resulting array

For example, let's consider subarray A = { 2, 8, 11} and subarray B = { 5, 6, 28} with three element each one.

We have to obtain the ordered resulting array R = { 2, 5, 6, 8, 11, 28}.

Let's apply the merge algorithm and see what's happening:

Merge algorithm applicator

 

Pseudocode

Generalizing we can distingue two phases:

Split phase

  • If the (sub)array has length 1--> stop the split phase
  • If the (sub)array has length > than 1 --> split in two parts (left and right)

function mergeSort(array)

//If the length(array)=1 --> stop the split phase

if(lenght(array)==1)

return array

//Else split in two parts (left and right), go ahead splitting and then Merge

else

split(array) = [left, right];

left = mergeSort(left)

right = mergeSort(right)

array = Merge(left, right)

return array

 

Merge phase

Merge the left and right (sub)array into a unique ordered array.

 

function Merge(left, right)

//Merge the list until at least one of them is empty

while notEmpty(left) and notEmpty(right)

//If the element of the array left is less or equal to the first of right, put it in the result array

if first(left) <= first(right)

append first(left) to result

//Else put the first right array element in the result array

else 

append first(right) to result

Programming languages implementation

C++

We are going to write two functions.

mergeSort

void mergeSort(int array[], int first, int last){
       //If the array contains only one element stop splitting
        if(first>=last)
        return;
       //Else go ahead splitting
       //Find the approximate middle
       //This formula is equal to (first+last)/2
       //But avoids overflow for large first and last 
       int middle = first + (last-first)/2;
       //Go ahead splitting the left side
       mergeSort(array, first, middle);
       //Go ahead splitting the right side
       mergeSort(array, middle+1, last);
       //Then merge them
       merge(array, first, middle, last);
}

merge

void merge(int array[], int first, int middle, int last){
    //Calculate the lenth of the support array tmp
    int length = last-first+1;

    int tmp[length];

    int startLeft = first;

    int startRight = middle+1;


    for(int i = 0; i<length; ++i){

        if(startLeft>middle){

            tmp[i] = array[startRight++];

        }

        else if(startRight>last){

            tmp[i] = array[startLeft++];

        }

        else if(array[startLeft]<=array[startRight]){

            tmp[i] = array[startLeft++];

        }

        else{

            tmp[i] = array[startRight++];

        }

    }

    for (int m=0; m< length; ++m){

        array[first++] =tmp[m];

    }


}

There are various ways to implement the Merge Sort algorithm. 

Try to implement it by yourself!

Complete program

//
//  MergeSort - Array Implementation - C++
//
//  Created by Andrea Cappelletti on 10/04/2018.
//
//  Explanation: https://www.cmprogrammers.com/post.php?id=51

#include 

//Define the constant size of the array
#define size 5

//Function Merge that combine the processed array
void merge(int array[], int& first, int& middle, int& last){
   
    int length = last-first+1;                          //Calculate the length of the support array tmp
    
    int* tmp = new int[length];                         //Inizialize tmp
    
    int startLeft = first;                              //Save the initial index of the left side array
    
    int startRight = middle+1;                          //Save the initial index of the right side array
    
    
    for(int i = 0; i<length; ++i){                      //Let's fill the ordered array tmp with a for cicle
         if(startLeft>middle){                          //We have finished to fill the right side of the array
             tmp[i] = array[startRight++];
        }
        else if(startRight>last){
            tmp[i] = array[startLeft++];                //We have finished to fill the left side of the array
        }
        else if(array[startLeft]<=array[startRight]){   //Each time we are going to add the minimum element
            tmp[i] = array[startLeft++];                //The left element is the least
        }
        else{
            tmp[i] = array[startRight++];               //The right element is the least
        }
    }
    
  
    
    //Let's save the ordered array and delete tmp
    for (int m=0; m< length; ++m){
        array[first++] =tmp[m];
        
    }
    delete [] tmp;
    
}

//This is the recursive function
void mergeSort(int array[], int first, int last){
    
    if(first>=last)                                    //Base case
        
        return;
    
    
    int middle = first + (last-first)/2;               //Calculate the middle of the array (avoiding the overflow)
   
    
    mergeSort(array, first, middle);                   //Let's call the function recursively
    
    mergeSort(array, middle+1, last);
    
    merge(array, first, middle, last);                 //And then...merge!
    
    
}

//This function allow us to print the array so we can check if the merge was successfull
void print(int array[]){
    for(int i = 0; i< size; i++){
        std:: cout <<array[i]<<" ";
        
    }
    std::cout<<std::endl;
}

//Main
int main(){
    int array[size]={4,6,3,2,1};                       //Let's fill our array of size defined in the beginning of the file
    std::cout<<"Array before mergeSort"<<std::endl;
    print(array);
    mergeSort(array, 0, size-1);
    std::cout<<"Array after mergeSort"<<std::endl;
    print(array);
}

The full code is available on my GitHub

Properties

The Merge Sort is the best sorting algorithms for a large amount of data. 

It is a stable algorithm, but it's not adaptative.

We can use it in every situation, in particular when we want to order linked list and when random access is much more expensive than sequential access.

Complexity

The merge sort is a really efficient algorithm for a large amount of input.

The time complexity can be expressed as following recurrence relation

 

T(n) = 2T(n/2) + Θ(n)

   

The complexity is Θ(log(n)) in each case (average, worst, best).