PYTHON : Merge Sort: Walkthrough, Code & Variants

on


 

Merge Sort: Walkthrough, Code & Variants

    Sorting is one of the most important concepts in computer science. Among all the sorting techniques, Merge Sort stands out for its efficiency and elegant divide-and-conquer approach. Let’s explore how it works, see it in action, and discuss its variants.

 What is Merge Sort?

Merge Sort is a divide and conquer algorithm that:

  1. Divides the unsorted list into smaller sublists until each list has only one element.

  2. Merges those sublists to produce new sorted sublists.

  3. Continues merging until there’s only one sorted list remaining.

Step-by-Step Walkthrough

Let’s sort the list:
[38, 27, 43, 3, 9, 82, 10]

Step 1: Divide the array into halves
[38, 27, 43, 3] and [9, 82, 10]

Step 2: Keep dividing until single-element arrays
[38] [27] [43] [3] [9] [82] [10]

Step 3: Merge and sort during combining

  • [38] + [27] → [27, 38]

  • [43] + [3] → [3, 43]

  • [9] + [82] + [10] → merge step-by-step → [9, 10, 82]

Step 4: Continue merging sorted halves
[27, 38, 3, 43] → [3, 27, 38, 43]
[9, 10, 82] stays as is

Step 5: Final merge
[3, 27, 38, 43] + [9, 10, 82] → [3, 9, 10, 27, 38, 43, 82]

Final Sorted Output: [3, 9, 10, 27, 38, 43, 82]

Python Code Implementation

def merge_sort(arr):
    if len(arr) > 1:
        mid = len(arr) // 2
        left_half = arr[:mid]
        right_half = arr[mid:]

        merge_sort(left_half)
        merge_sort(right_half)

        i = j = k = 0

        # Merge process
        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

        # Copy 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
arr = [38, 27, 43, 3, 9, 82, 10]
merge_sort(arr)
print("Sorted array:", arr)

Output:

Sorted array: [3, 9, 10, 27, 38, 43, 82]

Time and Space Complexity

Case Time Complexity
Best O(n log n)
Average O(n log n)
Worst O(n log n)

Space Complexity: O(n) — because of extra space used during merging.

Variants of Merge Sort

  1. Top-Down Merge Sort:
    The standard recursive version (as above).

  2. Bottom-Up Merge Sort:
    An iterative version that merges sublists from size 1 upwards, eliminating recursion.

  3. In-Place Merge Sort (Advanced):
    Tries to reduce extra space usage but is more complex and slower in practice.

Why Use Merge Sort?

  • Excellent for large datasets.

  • Stable sorting algorithm (preserves order of equal elements).

  • Works efficiently even for linked lists.

  • Performs consistently well (O(n log n)) in all cases.

 Summary

Feature Merge Sort
Type Divide & Conquer
Best Case O(n log n)
Worst Case O(n log n)
Space O(n)
Stability Stable
Use Case Large datasets, linked lists

Conclusion

Merge Sort might seem complex at first, but it’s one of the most efficient and reliable algorithms you’ll ever use. Whether you’re preparing for coding interviews or optimizing a real-world application, understanding Merge Sort is essential for every programmer.



Comments

Post a Comment