How to do Merge Sort in Python

Merge sort is one of the most efficient and reliable sorting algorithms, known for its divide-and-conquer approach. It is particularly useful for sorting large datasets due to its guaranteed O(n log n) time complexity, making it a popular choice in many applications. This blog post walks you through the implementation of merge sort in Python, provides a detailed visual explanation, and explores variations like bottom-up, in-place, parallel, and natural merge sort.

---

What is Merge Sort?

Merge sort is a divide-and-conquer sorting algorithm that recursively divides an array into smaller sub-arrays until each contains a single element. These sub-arrays are then merged back together in sorted order.

How Merge Sort Works:

1. Divide the array into two halves recursively until you have sub-arrays with one element.
2. Merge the sub-arrays by comparing elements and combining them in sorted order.
3. Repeat until all sub-arrays are merged and the entire array is sorted.

Time Complexity:

• Best Case: O(n log n) — The array is split and merged efficiently.
• Worst Case: O(n log n) — Performance remains consistent regardless of input order.

---

Merge Sort Algorithm in Python

Here’s a straightforward implementation of merge sort in Python:

def merge_sort(arr):
    if len(arr) > 1:
        mid = len(arr) // 2  # Find the middle of the array
        left_half = arr[:mid]  # Split into two halves
        right_half = arr[mid:]

        # Recursively sort both halves
        merge_sort(left_half)
        merge_sort(right_half)

        i = j = k = 0

        # Merge the sorted halves
        while i < len(left_half) and j < len(right_half):
            if left_half[i] < right_half[j]:
                arr[k] = left_half[i]
                i += 1
            else:
                arr[k] = right_half[j]
                j += 1
            k += 1

        # Check for remaining elements
        while i < len(left_half):
            arr[k] = left_half[i]
            i += 1
            k += 1

        while j < len(right_half):
            arr[k] = right_half[j]
            j += 1
            k += 1

# Example usage:
data = [12, 11, 13, 5, 6, 7]
merge_sort(data)
print("Sorted array:", data)

Output:

Sorted array: [5, 6, 7, 11, 12, 13]

---

Diagram Explanation of Merge Sort:

To understand merge sort visually, let’s take the example of sorting the array [12, 11, 13, 5, 6, 7]:

Step 1: [12, 11, 13, 5, 6, 7]  (Original array)

Step 2: Split into two halves:
        Left: [12, 11, 13]
        Right: [5, 6, 7]

Step 3: Recursively split each half:
        Left split: [12] | [11, 13] => [12] | [11] | [13]
        Right split: [5] | [6, 7] => [5] | [6] | [7]

Step 4: Merge sub-arrays:
        Left merge: [11, 12, 13]
        Right merge: [5, 6, 7]

Step 5: Merge the left and right halves:
        [5, 6, 7, 11, 12, 13]

---

Variations of Merge Sort

There are several interesting variations of merge sort, each optimizing different aspects of the algorithm for specific use cases. Let’s explore some of the most popular variations:

1. Bottom-Up Merge Sort

Bottom-up merge sort avoids recursion and iteratively merges sub-arrays of increasing size. It is useful when recursion overhead is a concern.

Bottom-Up Merge Sort Code

def bottom_up_merge_sort(arr):
    width = 1
    n = len(arr)
    while width < n:
        for i in range(0, n, 2 * width):
            left = arr[i:i+width]
            right = arr[i+width:i+2*width]
            arr[i:i+2*width] = merge(left, right)
        width *= 2

def merge(left, right):
    result = []
    i = j = 0
    while i < len(left) and j < len(right):
        if left[i] < right[j]:
            result.append(left[i])
            i += 1
        else:
            result.append(right[j])
            j += 1
    result.extend(left[i:])
    result.extend(right[j:])
    return result

# Example usage:
data = [12, 11, 13, 5, 6, 7]
bottom_up_merge_sort(data)
print("Sorted array (Bottom-Up):", data)

Output:

Sorted array (Bottom-Up): [5, 6, 7, 11, 12, 13]

2. Natural Merge Sort

Natural merge sort leverages the fact that data often contains already sorted sequences (runs). It identifies these runs and merges them, making it more efficient for datasets with naturally ordered subsequences.

Natural Merge Sort Code:

def natural_merge_sort(arr):
    runs = []
    new_run = [arr[0]]

    # Identify runs (naturally ordered subsequences)
    for i in range(1, len(arr)):
        if arr[i] >= arr[i - 1]:
            new_run.append(arr[i])
        else:
            runs.append(new_run)
            new_run = [arr[i]]
    runs.append(new_run)

    # Iteratively merge runs
    while len(runs) > 1:
        new_runs = []
        for i in range(0, len(runs), 2):
            if i + 1 < len(runs):
                new_runs.append(merge(runs[i], runs[i + 1]))
            else:
                new_runs.append(runs[i])
        runs = new_runs

    return runs[0]

def merge(left, right):
    result = []
    i = j = 0
    while i < len(left) and j < len(right):
        if left[i] < right[j]:
            result.append(left[i])
            i += 1
        else:
            result.append(right[j])
            j += 1
    result.extend(left[i:])
    result.extend(right[j:])
    return result

# Example usage:
data = [12, 11, 13, 5, 6, 7, 14, 15, 1, 2, 3]
sorted_data = natural_merge_sort(data)
print("Sorted array (Natural):", sorted_data)

Output:

Sorted array (Natural): [1, 2, 3, 5, 6, 7, 11, 12, 13, 14, 15]

3. Parallel Merge Sort

With the rise of multicore processors, parallel merge sort can leverage multiple threads to improve performance. The array is split and sorted concurrently across multiple cores, and the sorted sub-arrays are then merged in parallel. This can drastically reduce the sorting time for vast datasets.

4. In-Place Merge Sort

Standard merge sort requires O(n) extra space for merging, but in-place merge sort reduces this space complexity to O(1) by sorting the array in place. The implementation is more complex and may not perform as efficiently as the standard merge sort, but it conserves memory.

In-Place Merge Sort Code:

def merge_in_place(arr, start, mid, end):
    start2 = mid + 1
    # If already sorted, return
    if arr[mid] <= arr[start2]:
        return
    while start <= mid and start2 <= end:
        if arr[start] <= arr[start2]:
            start += 1
        else:
            value = arr[start2]
            index = start2
            while index != start:
                arr[index] = arr[index - 1]
                index -= 1
            arr[start] = value

            start += 1
            mid += 1
            start2 += 1

def in_place_merge_sort(arr, l, r):
    if l < r:
        mid = l + (r - l) // 2
        in_place_merge_sort(arr, l, mid)
        in_place_merge_sort(arr, mid + 1, r)
        merge_in_place(arr, l, mid, r)

# Example usage:
data = [12, 11, 13, 5, 6, 7]
in_place_merge_sort(data, 0, len(data) - 1)
print("Sorted array (In-Place):", data)

Output:

Sorted array (In-Place): [5, 6, 7, 11, 12, 13]

---

Limitations of Merge Sort

While merge sort is highly efficient, it does have certain limitations:

1. Requires Additional Memory: Merge sort needs O(n) additional space for auxiliary arrays. This can be an issue for large datasets when in-place sorting is necessary.
2. Not Ideal for Small Arrays: For small datasets, simpler algorithms like insertion sort can outperform merge sort due to lower overhead.
3. Slower in Practice: Even though merge sort has a better time complexity than algorithms like bubble sort, in practice, quick sort often outperforms it due to lower constant factors.

Conclusion

Merge sort is a powerful, stable, and reliable sorting algorithm with consistent O(n log n) performance. In this post, we explored various implementations of merge sort, including bottom-up, parallel, in-place, and natural merge sort, each suited to different scenarios. Merge sort is a great choice for sorting large datasets, especially when stability and guaranteed performance are needed. However, be mindful of the memory overhead and consider using other variations if necessary.

Congratulations on reading to the end of this tutorial!

For further reading on sorting algorithms in Python, go to the articles:

• How to do Insertion Sort in Python
• How to Do Bubble Sort in Python
• How to do Quick Sort in Python
• How to Do Selection Sort in Python
• How to do Counting Sort in Python
• How to Do Radix Sort in Python
• How to Do Bucket Sort in Python
• How to Do Heap Sort in Python
• How to Do Pigeonhole Sort in Python
• How To Do Comb Sort in Python 
• How to Do Shell Sort in Python

Go to the online courses page on Python to learn more about Python for data  science and machine learning.

Have fun and happy researching!