DEV Community

Shahriyar Al Mustakim Mitul
Shahriyar Al Mustakim Mitul

Posted on

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:

Image description
Now we have divided it into 2 halves:

Image description
Again we divide them:

Image description

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

Image description

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

Image description

Same for the next pair 3 & 7.

Image description

Image description

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

So, this will be merged in this order:

Image description

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

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

Image description

Image description

Image description

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

Image description

Image description

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
Enter fullscreen mode Exit fullscreen mode

Complexity Analysis

Image description

So, eventually the complexity is:

Image description

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.

Top comments (0)