Merge Sort Algorithm in Python | Explained

Merge Sort is a classic divide-and-conquer sorting technique. It divides the list into two halves, sorts each half recursively, and then merges the two sorted halves.

So let’s get started with the [Problem Link].

The major steps are:

1. Divide: Split the array into two parts.
2. Conquer: Recursively sort each half.
3. Combine: Merge the two sorted halves into a single sorted list.

This approach ensures a guaranteed time complexity of O(nlog⁡n) in the worst, average, and best cases, making Merge Sort a reliable and efficient sorting algorithm, especially for large datasets.

1. The merge_sort Function

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

    # Divide the array into two halves
    mid = len(arr) // 2
    left_half = arr[:mid]
    right_half = arr[mid:]

    # Recursively sort each half
    left_half = merge_sort(left_half)
    right_half = merge_sort(right_half)

    # Merge the sorted halves
    return merge_array(left_half, right_half)

Explanation

1. Base Condition: If the list has 0 or 1 elements, it’s already sorted, so return it as is.
2. Find Midpoint: Compute mid = len(arr) // 2 to split the array into two nearly equal halves.
3. Recursive Sort:
   • Recursively call merge_sort(left_half) and merge_sort(right_half).
   • This breaks each subarray further until it reaches the base condition (lists of size 1 or 0).
4. Merge: After both halves return in sorted form, pass them to merge_array to produce a single, sorted list.

2. The merge_array Function

def merge_array(left, right):
    merged = []
    i, j = 0, 0

    # Merge the two halves by comparing elements
    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 from the left subarray
    while i < len(left):
        merged.append(left[i])
        i += 1

    # Append remaining elements from the right subarray
    while j < len(right):
        merged.append(right[j])
        j += 1

    return merged

Explanation

1. Initialization: Create an empty list merged. Set pointers i and j to 0, indicating the current index in left and right, respectively.
2. Compare and Pick:
   • While both i < len(left) and j < len(right), compare left[i] and right[j].
   • Whichever element is smaller, append it to merged and move that pointer forward.
3. Collect Remaining:
   • If any elements remain in left after one of the lists is exhausted, append all of them.
   • Do the same for the remaining elements in right.
4. Result: merged now contains a sorted combination of the two sublists.

Also read about the Python Program to Implement Quick Sort Algorithm.

3. Putting It All Together

Initial Array:

arr = [64, 34, 25, 12, 22, 11, 90]
sorted_arr = merge_sort(arr)
print(f"Sorted array = {sorted_arr}")

Call merge_sort(arr):

1. Splits arr into two halves.
2. Recursively sorts each half.
3. Merges them via merge_array.

Final Output:

Sorted array = [11, 12, 22, 25, 34, 64, 90]

4. Dry Run Example

Let’s dry run a smaller sub-problem: [34, 25, 11].

1. Split:
   • Left: [34]
   • Right: [25, 11]
2. Recursively Sort Left: [34] is a single element, so it’s already sorted.
3. Recursively Sort Right: Split [25, 11] into [25] and [11], both single elements.
   • Merge [25] and [11] → [11, 25].
4. Merge:
   • Merge [34] and [11, 25].
   • Compare 34 with 11 → take 11. Next compare 34 with 25 → take 25. Finally, take 34.
   • Final merged list: [11, 25, 34].

5. Time & Space Complexity

1. Time Complexity:
   • Each time we split the list into two halves and then merge them.
   • The depth of recursion is about log⁡n.
   • At each level, merging all elements takes O(n).
   • Overall time complexity: O(n.log⁡n).
2. Space Complexity:
   • We allocate extra space for the sublists and for merging.
   • Overall space complexity: O(n) in most implementations.

6. Key Takeaways

1. Divide-and-Conquer: Merge Sort systematically splits the array and merges results.
2. Consistent Performance: It guarantees O(nlog⁡n) even in the worst case.
3. Stable Sorting: Merge Sort preserves the order of equal elements, which can be advantageous in certain scenarios.

Requires Extra Space: Unlike in-place sorts, Merge Sort needs additional memory to merge sublists.

For any changes to the article, kindly email at code@codeanddebug.in or contact us at +91-9712928220.