DSA by Mitul in C++, Python, and Java : Merge Sort (Divide & Conquer Algorithm)

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:

Now we have divided it into 2 halves:

Again we divide them:

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

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.

Same for the next pair 3 & 7.

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.

So, this will be merged in this order:

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.

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

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.

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

So, eventually the complexity is:

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.