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

## Top comments (1)

Nice