**Merge sort** is a **comparison-based sorting** algorithm that follows a **divide and conquers paradigm** to sort the elements in ascending or descending order. Though it is a comparison based sorting technique, it is different from bubble or selection sort. The logic may be little complicated than those sorting technique but this sorting technique are **better in terms of time complexity** and the number of comparisons is also less than them. The space complexity of this algorithm is more than some other sorting techniques as it needs **2n space to sort n no. of data**.

**The procedure with an** **example:**

Suppose there is an array of **7 elements** as following and it has to be sorted in **ascending order**:

**Step 1:** According to the logic of **merge sort the array will be divided ****into two halves** then the **sub-arrays will again be divided into two halves** and so on **until it reaches all single element arrays**. So for the above example, the array will first be divided into two halves as follows:

**Half 1: **

**Half 2:**

**Step 2:**

In the next step, the **1st half**** will again be divided into two arrays**, the **first array** will contain the **elements ****45 **and **36**, the **second array** will contain the **elements ****12** and **75**. The **2nd half** will **also be divided into two arrays** in which the **first array** will **contain ****2**** and ****19 **and the **2nd array** will have only **one element i.e. ****25**.

After this step, we will get the arrays as:

**Step 3:**

In this step **we will get all single element arrays** as **these above pairs of elements will again be divided into halves and for ****n number of elements**** into ****n number of arrays**** **will be formed. As here the number of elements is 7 so we will get 7 single element arrays as:

This is the division part of the **divide and conquers paradigm** now the elements will be conquered again by reversing the division rule and at the time of conquering the sorting will be performed and the sorted elements will be stored into another array.

**Step 4:**

First, **the first two single-element arrays will be compared** and will be conquered in sorted order. For this example**, ****45**** and ****36**** will be compared**. As **45**** is greater than ****36**, **36 will be inserted into the other array**. Similarly, **12 **and **75** will be compared and will **be inserted according to** their** sorted order**. Then **2** and **19** will be **compared and inserted in sorted order**. 25 will be inserted at the last. So after conquering for the first time the arrays will be:

**Step 5:**

Now **36**** will be compared to ****12**, as **12 < 36** then **12 ****will be inserted into the other array** where the sorted array will be stored. After that **36**** will again be compared** with **75 **and as **36 < 75** so **36**** will be inserted into the sorted array**. **Lastly**,** ****45 ****and ****75 ****will be compared** and will be inserted into the sorted array according to their sorted order. After this the conquered array will be:

Similarly, the next two pairs of the array will be compared and the conquered array will be:

**Step 6:**

At the **last step of conquering**, here we compare elements of two lists one by one. **12**** will be compared to ****2**. **As ****2**** is less than ****12**, **2** will be **inserted first in the sorted array**. After that **12 ****is again compared to ****19,** in this case as **12**** is lesser than ****19**, **12** is **inserted into the sorted array**. Now **19** and **36** are **compared **and **19 ****have been inserted into the sorted array**, then **25 ****and ****36**** are compared** and **25**** are inserted into the sorted array**. After this, there is **no unsorted element in the 2nd half** of the array. So in this situation, all the rest elements of the first half will be inserted into the sorted array without any comparisons as already the elements of that half are sorted.

**Lastly, we will get the final sorted array as**:

**Divide and conquer procedure by tree:**

```
MERGE (A, p, q, r)
{ n_1=q-p+1
n_2=r-q
Let L[1 ……. n_1 + 1] and R[1 to n_2 + 1] be new arrays
for(i = 1 to n_1)
{
L[i] = A[p + i – 1]
}
for(j = 1 to n_2)
{
R[j] = A[q + j]
}
L^' [n_1+1]=∞
R[n_2+1]=∞
i = 1, j = 1
for(k = p to r)
if(L[i] <= R[j])
A[k] = L[i]
i = i + 1
else A[k] = R[j]
j = j + 1
}
```

```
Merge_sort(A, p, r)
{ if(p < r)
{ q = ⌊(p + r)/ 2⌋ // mid point
Merge_sort(A, p, q)
Merge_sort (A, q + 1, r)
Merge (A, p, q, r)
}
}
```

__CHARACTERISTICS of Merge Sort:__

**1. **It is based on the divide and conquers paradigm.

**2. **It is a comparison-based sorting technique.

**3. **Merge sort is faster than the insertion sort technique.

**4. **It is a comparison-based sorting algorithm.

**5. **It is a stable sorting technique.

__TIME COMPLEXITY:__

**Merge_sort(A, p, r)** _______________ **T(n) (Let)**

{ if(p < r)

{ q = ⌊(p + r)/ 2⌋ // **mid point**

**Merge_sort(A, p, q)** _____________ **T(n/2)**

**Merge_sort (A, q + 1, r)** _________ **T(n/2)**

**Merge (A, p, q, r)** _________________ **O(n)**

}

}

So,

**[****For details please see **__masters theorem__** and **__substitution method__** to calculate time complexity of a recursive algorithm****]**

** **

**Here we solve it by master theorem: **

**Master Theorem: **

**And in this case one condition has satisfied that is: **

And also **p > -1**, **then ** [for details please follow the ** master theorem**]

If we **put the value of ****a****, ****b**,** ****and ****p**** **we will get:

__SPACE COMPLEXITY:__

In **merge sort**, it always divides the array from the middle position, so, total division tree of the sorting process will be always balanced.

In the case of a balanced tree, we know the **number of ****stacks ****required to solve this recursion is ****equal to**** ****height of the tree**. And **height of the balanced tree** **for n number** is ** ****log n**.

And **space complexity** to **merge two arrays into single array of size ****n**.

__ADVANTAGES of merge sort:__

**1. **It sorts a large array very quickly.

**2. **Time complexity is lesser than a bubble or selection sort.

**3. **It is a stable sorting technique.

**4. **It has a consistent running time.

**5. **It can be executed using a parallel computing technique.

__DISADVANTAGES of merge sort:__

**1. **It is **not an in-place algorithm** i.e. it requires extra memory space for sorting.

**2. **It is slower than the other sorting techniques for smaller data.

**3. **It performs the whole process if the array is sorted just like other sorting techniques.

Related

- Quick Sort using recursion
- Quicksort Iterative
- Insertion Sort
- Selection Sort
- Bubble Sort
- Merge Sort Iterative
- 3 way Merge Sort
- Heap Sort using recursion
- Heap Sort Iterative
- Radix Sort for positive integer
- Bucket Sort
- Counting Sort
- Cocktail Sort
- Intro Sort
- Minmax Sort
- List Sort
- Tree Sort
- Shell Sort
- Gnome sort
- Comb Sort
- Bitonic Sort
- Tim Sort

Contributed by