Merge Sort in Python: The Ultimate Guide

If you’re a programmer or data scientist, you’ve probably heard of the merge sort algorithm. Merge sort is a popular and efficient sorting algorithm widely used in computer science. In this guide, we’ll explore what merge sort is, how it works, and how to implement it in Python.

What is Merge Sort?

Merge sort is based on a divide-and-conquer principle. This works by breaking down the array into smaller subarrays, sorting those subarrays, and then merging them back together. Once you will follow the below example with python code, it will be more precise.

Merge Sort Visualization – Source – Wikipedia

What is Merge Sort Used For?

Merge sort is commonly used for sorting large datasets, as it is efficient and fast, even for very large arrays. It’s also useful for parallel sorting, where multiple processors can be used to sort the data.

Implementation of Merge Sort in Python

Following the python code to implement merge sort in Python. The time complexity of merge sort is O(n*log n) where n is the number of elements in the array.

def mergeSort(array, asc=True):
    '''
    Time complexity : O(nlog(n)))
    parameters:
        array   : Array of numbers to be sorted
        asc     : boolean flag to sort ascending
                  descending. Default = True (ascending)
    '''
    midIdx = len(array) // 2
   
    if len(array) == 1:
        return array
    
    leftArr = array[:midIdx]
    rightArr = array[midIdx:]
    # Double recursion
    # 1. To keep on dividing the entire
    #    in half until only one item is left
    #    in both left and right side arrays
    # 2. Each time those sub-arrays will be passed
    #    in the other recursive function, whihc will 
    #    return the sorted sub array.
    return sortArray(mergeSort(leftArr, asc), mergeSort(rightArr, asc), asc)
    
def sortArray(leftArray, rightArray, asc):
    sortedArray = [None] * (len(leftArray) + len(rightArray))
    i=j=k=0
    while i < len(leftArray) and j < len(rightArray):
        # based on ascending or descending order
        if asc:
            if leftArray[i] <= rightArray[j]:
                sortedArray[k] = leftArray[i]
                i += 1
            else :
                sortedArray[k] = rightArray[j]
                j += 1
        else:
            if leftArray[i] >= rightArray[j]:
                sortedArray[k] = leftArray[i]
                i += 1
            else :
                sortedArray[k] = rightArray[j]
                j += 1
        k += 1
    
    while i < len(leftArray):
        sortedArray[k] = leftArray[i]
        i += 1
        k += 1
    while j < len(rightArray):
        sortedArray[k] = rightArray[j]
        j += 1
        k += 1
    
    return sortedArray

if __name__ == "__main__":
    arrayToSort = [4, 6, 1, 10, 8, 9, 50, 7, 56]
    print("Array in ascending order :", mergeSort(arrayToSort))
    print("Array in descending order :", mergeSort(arrayToSort, asc=False))

Visual representation of Merge Sort

This example shows how merge sort can be used to sort an array of integers in Python. The algorithm divides the array in half, sorts each half recursively, and then merges the sorted halves back together. Refer to the below-animated visualization gif [from Wikipedia] which explains the process of divide and conquer sorting algorithm which is also called merge sort.

Merge Sort Visualization - Source - Wikipedia

Is Merge Sort Faster Than Quicksort?

The time complexity of merge sort is O(n*log n), where n is the number of elements in the array. This means that the time required to sort the array increases logarithmically with the number of elements. Both merge sort and quicksort are efficient sorting algorithms, but they have different strengths and weaknesses. Merge sort is generally considered to be more efficient for sorting large datasets, while quicksort is better for small to medium-sized datasets.

Why is Merge Sort More Effective?

Merge sort has several advantages over other sorting algorithms, such as:

1. It is highly scalable and can handle large datasets.
2. It is a stable sorting algorithm that maintains the relative order of equal elements.
3. It is easy to implement and understand.