Skip to content

Implementing Merge Sort in Python - A Step-by-Step Guide

Updated: at 04:45 AM

Merge sort is an efficient, stable sorting algorithm that works by recursively dividing an array into smaller subarrays, sorting each subarray, and then merging them back together in a sorted order. It has a time complexity of O(nlogn) and space complexity of O(n), making it faster than quadratic sorting algorithms like bubble sort and insertion sort.

In technical interviews, candidates are often asked to implement common algorithms like merge sort to evaluate their coding skills and analytical thinking. This article will provide a step-by-step guide on implementing merge sort in Python. We will cover the following:

Table of Contents

Open Table of Contents

Overview of Merge Sort

Merge sort is a divide-and-conquer algorithm that recursively splits an array into smaller subarrays, sorts each subarray, and then merges them back to produce the final sorted array. It operates in a bottom-up approach as follows:

  1. If the array has 0 or 1 elements, it is already sorted - return the array
  2. Otherwise, split the array recursively into two halves until each subarray has 1 element
  3. Sort and merge the subarrays in a bottom-up manner until the full array is sorted
  4. Return the sorted full array

The key steps are:

This “divide and conquer” strategy allows merge sort to efficiently sort the array in O(nlogn) time complexity. The tradeoff is it requires extra O(n) space complexity to store the divided subarrays temporarily during the merge phase.

Python Implementation of Merge Sort

Here is a step-by-step implementation of merge sort in Python:

1. Recursive Merge Sort Function

We first define a recursive merge_sort function that takes in an array and recursively divides it into halves:

def merge_sort(arr):
    # Base case
    if len(arr) <= 1:
        return arr

    # Recursively divide array into halves
    mid = len(arr) // 2
    left = merge_sort(arr[:mid])
    right = merge_sort(arr[mid:])

    # Merge the sorted halves
    return merge(left, right)

2. Merge Function

The merge function merges the two sorted subarrays:

def merge(left, right):
    # Create an empty list to store the merged values
    merged = []

    # Iterate over left and right lists until one is empty
    i, j = 0, 0
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            merged.append(left[i])
            i += 1
        else:
            merged.append(right[j])
            j += 1

    # Append remaining elements if any
    merged += left[i:]
    merged += right[j:]
    return merged

3. Driver Code

The driver code calls the merge sort function on the array:

arr = [5,4,3,2,1]
print(merge_sort(arr))

# Output: [1,2,3,4,5]

We can now use the merge_sort function to sort any arrays in Python.

Analysis of Merge Sort in Python

Let’s analyze the time and space complexity of this implementation:

Time Complexity

Space Complexity

Therefore, this implementation has optimal O(nlogn) time with a tradeoff of using auxiliary O(n) space.

Testing the Merge Sort Implementation

We can test our implementation with different input arrays to verify it works correctly:

import random

arr1 = [5,4,3,2,1]
arr2 = list(reversed(range(10)))
arr3 = [random.randint(1,30) for _ in range(20)]

print(merge_sort(arr1)) # [1,2,3,4,5]
print(merge_sort(arr2)) # [0,1,2,3,4,5,6,7,8,9]
print(merge_sort(arr3)) # Sorted array

We test it on a descending array, ascending array, and random array of integers to ensure it correctly sorts arrays of different sizes and distributions.

Applications and Use Cases of Merge Sort

Merge sort is useful in many applications:

Overall, merge sort is a versatile sorting algorithm commonly used in data analysis, databases, data science, and other backend applications.

Comparison with Other Sorting Algorithms

How does merge sort compare with other common sorting algorithms?

So in summary, merge sort provides a good balance of time performance, stability, and parallelizability for sorting large arrays where auxiliary space is available.

Conclusion

Implementing merge sort from scratch is a common technical interview coding challenge assessing knowledge of algorithms. This guide covered a step-by-step Python implementation with complexity analysis, testing, use cases, and comparisons.

Key points to remember:

With this comprehensive walkthrough, you should now be able to implement merge sort efficiently in Python and have a deeper understanding of its algorithmic foundations that can be applied in technical interviews and coding challenges.