All About Merge Sort Algorithm
Tags: algorithms, sorting, mergesort, problemsolving
Published: 2021-05-15 20:09:18

##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} :-

![Alt Text](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/pr1fa43ifd85blqillrf.png)

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 :-).