How to Implement Merge Sort in Python

1. Use Recursion to Implement Merge Sort in Python
2. Use Iterative Merge Sort in Python

Merge sort is a popular sorting algorithm utilized to sort the elements of any given data structure. This tutorial discusses the merge sort algorithm and how to implement it in Python.

Merge sort is a prime example of the divide-and-conquer approach and is utilized to sort large data sets. The algorithm begins by dividing the given data structure into two parts and then repeats the same process on both halves. Finally, it combines the halves back together to obtain sorted values efficiently. Hence, we call it a prime example of the divide-and-conquer approach.

The best part about this algorithm is that it has a consistent time complexity of O(nlogn) in all three possible cases (average case, best case, and worst case). Due to this fact, it is generally considered efficient and is preferred for large data sets.

We will now see how to implement the merge sort algorithm using the Python programming language.

Use Recursion to Implement Merge Sort in Python

Merge sort is simply implemented in Python with the help of a recursive function.

The following code uses recursion to implement merge sort in Python.

def m(left, right):
    if not len(left) or not len(right):
        return left or right

    result = []
    i, j = 0, 0
    while len(result) < len(left) + len(right):
        if left[i] < right[j]:
            result.append(left[i])
            i += 1
        else:
            result.append(right[j])
            j += 1
        if i == len(left) or j == len(right):
            result.extend(left[i:] or right[j:])
            break

    return result


def msort(list):
    if len(list) < 2:
        return list

    middle = int(len(list) / 2)
    left = msort(list[:middle])
    right = msort(list[middle:])

    return m(left, right)


lst = [5, 9, 3, 7, 15, 6]
print("Given List:")
print(lst)
print("\n")
print("Sorted List:")
print(msort(lst))

The above code provides the following output:

Given List:
[5, 9, 3, 7, 15, 6]
Sorted List:
[3, 5, 6, 7, 9, 15]

Code Explanation:

• The given list is separated into two halves, left and right in every recursive call as long as two adjacent values are not obtained.
• The m() function is created and utilized to merge the two halves that are originally divided in the first step.
• The msort() function carries out most of the dividing and the sorting part of the given list in the program.

Use Iterative Merge Sort in Python

The iterative merge sort algorithm is a little different from the general recursive method as the former makes use of the bottom-up approach while the latter uses the top-to-bottom approach. However, the time complexity and the final answer remain exactly the same in both methods.

Moreover, the recursive merge sort method makes use of an explicit auxiliary stack, while there is no need for it in the iterative merge sort algorithm implementation.

The following code uses the iterative merge sort algorithm to implement merge sort in Python.

def msort(a):
    width = 1
    n = len(a)
    while width < n:
        l = 0
        while l < n:
            r = min(l + (width * 2 - 1), n - 1)
            m = (l + r) // 2
            if width > n // 2:
                m = r - (n % width)
            mer(a, l, m, r)
            l += width * 2
        width *= 2
    return a


def mer(a, l, m, r):
    n1 = m - l + 1
    n2 = r - m
    L = [0] * n1
    R = [0] * n2
    for i in range(0, n1):
        L[i] = a[l + i]
    for i in range(0, n2):
        R[i] = a[m + i + 1]

    i, j, k = 0, 0, l
    while i < n1 and j < n2:
        if L[i] > R[j]:
            a[k] = R[j]
            j += 1
        else:
            a[k] = L[i]
            i += 1
        k += 1

    while i < n1:
        a[k] = L[i]
        i += 1
        k += 1

    while j < n2:
        a[k] = R[j]
        j += 1
        k += 1


a = [5, 9, 3, 7, 15, 6]
print("Given List:")
print(a)
msort(a)
print("Sorted List:")
print(a)

The above code provides the following output:

Given List:
[5, 9, 3, 7, 15, 6]
Sorted List:
[3, 5, 6, 7, 9, 15]

Disadvantages of Merge Sort

Even though merge sort is really popular and is considered to be highly efficient, it has some drawbacks in various cases, which are mentioned below.

• When dealing with a smaller set of data structures, it can be comparatively slower than the other available sorting algorithms.
• Extra memory space is needed to implement this algorithm.
• The algorithm will always go through with the whole process, even when the given data structure is already sorted.