Merge Sort vs. Quick Sort

Why Two Sorting Algorithms?

Think of sorting a hand of playing cards. One approach: split the hand in half, give each half to a friend, have them sort their half, then carefully interleave the two sorted halves back together. That's Merge Sort. Another approach: pick one card as a reference point, put all lower cards to its left and all higher cards to its right, then repeat for each sub-group. That's Quick Sort. Both reach the same destination but via fundamentally different paths — and those paths have different costs.

The Stability Trade-off

Merge Sort:

• Mechanism: Divide and Conquer. Splits the list in half recursively until single elements remain, then merges sorted halves back together.
• Pros: Stable (preserves the relative order of equal elements), consistent $O(N \log N)$ worst-case, predictable performance.
• Cons: Requires $O(N)$ extra space for the temporary merge buffer — not in-place.

def merge_sort(arr):
    if len(arr) <= 1:
        return arr
    mid = len(arr) // 2
    left = merge_sort(arr[:mid])
    right = merge_sort(arr[mid:])
    return merge(left, right)

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

Quick Sort:

• Mechanism: Partitioning. Picks a pivot, rearranges elements so all smaller values are left of the pivot and all larger values are right, then recurses on each partition.
• Pros: In-place (low memory overhead, $O(\log N)$ stack space), often faster in practice due to cache locality — elements are accessed sequentially in memory.
• Cons: Unstable, worst-case $O(N^2)$ if the pivot is consistently bad (e.g., always picking the minimum element of an already-sorted array).

Interview Pivot Selection:
Never pick the first or last element as the pivot in an interview. Always pick a random element or the "median of three" (median of arr[left], arr[mid], arr[right]) to avoid the $O(N^2)$ worst-case scenario. Python's built-in sort() uses Timsort, which is a hybrid of Merge Sort and Insertion Sort and is always stable.