DSA by Mitul in C++, Python, and Java : Merge Sort (Divide & Conquer Algorithm)
Published: 2022-11-11 00:26:32

Here we will divide the input array in two halves and we keep halving recursively until they become too small that can not be broken further. Finally, we merge halves sorting them.
So, this is our array:

![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/ed2cevo4lu08r94z0771.png)
Now we have divided it into 2 halves:

![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/faa5blp0i9gro3e6nck4.png)
Again we divide them:

![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/zq9vus4upp0ccijwkenq.png)

Again we divided in 2 parts for each array left unless we have 1 value in each array.

![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/b8q7qyuk6aizjvxli1ka.png)


Now! The most important part. We have to merge the values which are in pair. But while merging we will compare and merge in a ordered way.
So, we will start with the pair 4 & 6. 4 is less than 6 thus we will merge them in the right order.

![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/sck0xrlx8vt427gp86ap.png)


![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/vwxun0ia8zwplamt4t6k.png)


Same for the next pair 3 & 7.


![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/ae7h501cq4z1f8mt2myh.png)

![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/sg77z1e8ohsdpdri4tbw.png)

Again, the most important part. As 4,6,3,7 came from the same array which we divided and made these pairs. We will now think (4,6) & (3,7) as a pair . We will make them in right order and then merge it.


![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/gexupm0etgt0gtpjo4g3.png)

So, this will be merged in this order:


![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/uwc386lpfgz0kgwvpc2j.png)

Remember what basically happened. We had a big array and we divided it into 2 array. look 1 part is sorted now . We will now sort another part.


![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/rth836o9s8bkue9wpusd.png)


Let's wait till the part 2 gets sorted and returns their home 😉.

![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/tqorbjc4bgsgtzpf0uwo.png)

![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/qn8ydtjezd9nqu8bd24y.png)


![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/k3acbex31xdn3ng4vtr0.png)

See, we have got our part 1 & part 2.
Now treat them as 2 values in a pair. Thus compare them and merge values in the sorting order to the main list.


![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/oybts9sugm98kbcmehx9.png)


![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/vtxbh5lawet20q85v2ux.png)



![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/q1ugjphflyf5khmqqsnm.png)

Done!!!

**Code for the merge sort**

```
def merge(customList, l, m, r):
    n1 = m - l + 1
    n2 = r - m

    L = [0] * (n1)
    R = [0] * (n2)

    for i in range(0, n1):
        L[i] = customList[l+i]
    
    for j in range(0, n2):
        R[j] = customList[m+1+j]
    
    i = 0 
    j = 0
    k = l
    while i < n1 and j < n2:
        if L[i] <= R[j]:
            customList[k] = L[i]
            i += 1
        else:
            customList[k] = R[j]
            j += 1
        k += 1
    while i < n1:
        customList[k] = L[i]
        i += 1
        k += 1
    
    while j < n2:
        customList[k] = R[j]
        j += 1
        k += 1

def mergeSort(customList, l, r):
    if l < r:
        m = (l+(r-1))//2
        mergeSort(customList, l, m)
        mergeSort(customList, m+1, r)
        merge(customList, l, m, r)
    return customList
```


**Complexity Analysis**


![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/wjlkteosh4g72e33cmq2.png)

So, eventually the complexity is:

![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/uvem6esq65p1h7nsvkvf.png)


**When to use merge sort?**
1. When we need stable sort(The values remain in order).
2. When average expected time is O(nlogn)

**When to avoid Merge sort?**
When space is a concern as we have O(n) space complexity.