All About Merge Sort Algorithm

Introduction to Merge Sort Algorithm

1. Merge Sort works on the Priciple of Divide And Conquer Algorithm to sort the group of element.

Question :- What do you understand by the term Divide And Conquer?

Answer :- Divide And Conquer follows these three steps :-

1.Divide refers to dividing the main Problem into Sub-Problem.

2.Conquer refers to solving the Sub-Problems.

3.Combine refers to combining the Solution of Sub-Problem to get the Solution of main Problem.

2. It is a Stable Algorithm .

Question :- What is the meaning of Stable ?

Answer :- Suppose , We are Sorting the Array in which there are two element which are same , In this case , What Merge sort Algorithm does that It maintains the original order if it finds two same element in an Array.

3. The Time complexity for Merge Sort Algorithm :-

Worst Case :- O(n*logn)

Averge Case :- O(n*logn)

Best Case :- O(n*logn)

4. The Auxiliary Space for Merge Sort Algorithm is O(n).

Working of Merge Sort Algorithm

*Here are the following steps that Merge Sort follows :-

1. Take two variable that hold the index of starting and last index of the array and take another variable that hold the value of middle index of the array.

2. The index value of left half of array will be from low to mid and the index value of right half of array will be from mid+1 to high.

3. Now , Divide the array into two halves (i.e Left and Right Half).

4. Repeat this untill you get single element in both (left and right half).

5. After this , With the help of Merge function of Merge Sort Algorithm will compare , sort and Merge the array of element of both halves(i.e left and right half).

Now ,let's look at the code of Merge Function of Merge Sort Algorithm :-

void merge(int array[] , int low , int mid , int high)
{
    int n1 = mid - low + 1 ;

    //n --> size of array of left half

    int n2 = high - mid ;

    //n2 --> size of array of right half

    int left[n1];

    //Array of left half

    int right[n2];

    //Array of right half

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

        left[i] = array[low+i];

        //storing the left half of array into a temporary array

    }

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

        right[i] = array[n1+i];

        //Storing the right half of array into a temporary array

    }

    //Till now , we have setup the Auxiliary space for our Array

    //Now , We will compare the element in both in left and right 

    //half And insert that element in the original which is 

    //smaller

    int i=0,j=0,k=0;

    while(i<n1 && j<n2){// Here , we are traversing both the array

    //If we have traversed any of the array otherone is not fully 

    //traversed yet , then we will come out of this loop 

        if( left[i] <= right[j] ){

        //If the element in left half is smaller than the element

        //in right half , then insert and insert the index value 

        //of left half and original array 

            array[k] = left[i];

            i++;

            k++;

        }

        else{

        //Else Insert the element of right half and increase the

        //index value of right half and original array

            array[k] = right[j];

            j++;

            k++;

        }

    }

    //If the above loop ends , Before traversing the both Array

    //then we will traverse that array which is not traverse 

    //completly yet and insert the elements of that array in to

    //original Array inthe same order.

    while(i<n1){

        array[k] = left[i];

        i++;

        k++;

    }

    while(j<n2){

        array[k] = right[j];

        j++;

        k++;

    }

}

Now let's give a walkthrough of working of Merge Sort Algorithm using the example of this Array , arr[] = {14,7,3,12,9,11,6,12} :-

So, here in the above walkthrough ,we labelled the low index as p ,high index as r and mid index as q . So ,Now firstly look at the code of Merge Sort Algorithm then we will cover both the code and the walkthrough .

Implementation of Merge Sort Algorithm :-

void mergesort( int array[] , int low ,int high ){
    if( high > low ){

        //we will recursively call this mergesort function    

        //for the left and right half of the array untill 

        //the high index is greater than the low index

        int mid_index = low + ( high - low )/2;

        mergesort(array,low,mid_index);

        //This recursive call is for left half of Array

        mergesort(array,mid_index+1,high);

        //This recursive is for right half of Array

        merge(array,low,mid_index,high);

        //The above call is to merge function compare and 
        //sort and merge the array 

    }

}

So ,When we apply the merge sort algorithm to above given array ,It does these steps :-

1. Find the middle index and divide the whole array into two halves ( left and right halves ).

2. BY call the merge sort function for the left and right half of the array.

3. When the high index is less than or equal to low index then we stop call the merge sort function.

4. Now ,We call the merge fucntion to compare , sort and merge the array.

And that's how we got the sorted Array...

Analysis of Merge sort Algorithm

1. The recursive calling part of merge sort fucntion takes O(1) time to break the array in two halves.

2. But the merge fucntion of merge sort algorithm take O(n) time to compare , sort and merge the array.

3. Now , Suppose there are x levels in your tree and at each level you are doing the work in O(n) time then the total time taken by this algorithm is :---

              T(n) = x * O(n)

Here, x is no. of level in the tree , So As we are dividing the array into two halves again and again untill we got single element ,So For this , The time taken by the algorithm to divide the array into two halves is O(log2n).

4. So , The Total time taken by the algorithm :--

              T(n) = O(n*logn)

So with this , I will wrap-up this post , I hope you understand the whole Algorithm .

Thankyou so much for Reading the post :-).