Sorting

Merge Sort

TimeO(n log n) SpaceO(n)

Imagine sorting a shuffled deck of cards. You split the deck in half, have two friends each sort their half, then you merge the two sorted halves by repeatedly picking the smaller top card. Your friends do the same thing recursively until they’re holding one card each — which is already sorted.

When to use it: You need a guaranteed O(n log n) sort, especially when stability matters (equal elements keep their original order). Also the go-to when sorting linked lists.

Key insight: Merging two sorted arrays is easy and fast — O(n). The recursion gives you log n levels of merging. Total: O(n log n), guaranteed.

Common trap: Forgetting that merge sort needs O(n) extra space. If memory is tight, consider an in-place sort like heap sort.

function mergeSort(arr):
    if length(arr) <= 1:
        return arr

    mid = length(arr) / 2
    left = mergeSort(arr[0..mid-1])       # sort left half
    right = mergeSort(arr[mid..end])       # sort right half

    return merge(left, right)

function merge(left, right):
    result = []
    i = 0, j = 0

    while i < length(left) and j < length(right):
        if left[i] <= right[j]:           # <= preserves stability
            result.append(left[i])
            i = i + 1
        else:
            result.append(right[j])
            j = j + 1

    # Append remaining elements
    result.append(left[i..end])
    result.append(right[j..end])

    return result

def merge_sort(arr: list[int]) -> list[int]:
    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: list[int], right: list[int]) -> list[int]:
    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


def count_inversions(arr: list[int]) -> tuple[list[int], int]:
    """Count inversions using modified merge sort."""
    if len(arr) <= 1:
        return arr, 0

    mid = len(arr) // 2
    left, left_inv = count_inversions(arr[:mid])
    right, right_inv = count_inversions(arr[mid:])

    merged = []
    inversions = left_inv + right_inv
    i = j = 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])
            inversions += len(left) - i  # all remaining left elements are inversions
            j += 1

    merged.extend(left[i:])
    merged.extend(right[j:])
    return merged, inversions

Problem: Given an array, count the number of "inversions" — pairs (i, j) where i < j but arr[i] > arr[j].

How would you approach this?

Answer: This is a modified merge sort problem. During the merge step, whenever you pick an element from the right half over the left, all remaining left-half elements form inversions with it. This counts all inversions in O(n log n).

Problem: Sort a linked list in O(n log n) time with O(1) extra space (beyond recursion stack).

How would you approach this?

Answer: This is merge sort on a linked list. Unlike arrays, linked lists can be merged in-place by rewiring pointers. Use slow/fast pointers to split, recursively sort, and merge.

Time: O(n log n) in all cases (best, average, worst). The array is split log n times, and each level of the recursion does O(n) work in the merge step. This guarantee is what makes merge sort reliable.

Space: O(n) because each merge creates a temporary array to hold the merged result. The recursion stack adds O(log n), but the dominant cost is the auxiliary array.