Merge Sort and Inversion Counting

Merge sort splits the array in half, sorts each half recursively, and merges the two sorted halves. It always runs in O(n log n), it is stable, and it is the natural way to sort linked lists. In interviews it matters as much for its merge step as for sorting: counting inversions and "how many smaller elements are to my right" are solved by counting during the merge.

Intuition

• Merging two sorted lists takes linear time: repeatedly compare the two front elements and move the smaller one to the output. When one list runs out, append the rest of the other.
• Divide and conquer: a list of length 0 or 1 is sorted. Otherwise sort both halves and merge them. The recursion has log2 n levels and each level merges n elements in total, so T(n) = 2T(n/2) + O(n) = O(n log n) in every case.
• Stability: when the two front elements are equal, take the one from the left half first (<=, not <). Equal keys then keep their original order.
• Counting while merging: when an element from the right half is placed before the remaining elements of the left half, each of those remaining elements was originally before it and is larger. That is exactly one inversion per remaining left element, and the merge discovers them in bulk.

When to use it in interviews / OAs

• You need a stable sort or a guaranteed O(n log n) worst case (quicksort only promises it on average).
• Sorting a linked list: merging only relinks nodes, needs no random access and no extra arrays.
• Counting pairs with an order condition (i < j and some inequality between a[i] and a[j]): inversions, "count smaller numbers after self", "reverse pairs" (a[i] > 2 * a[j]), counting range sums. Merge sort and a Fenwick tree are the two standard O(n log n) tools.
• Merging sorted sequences: merge two sorted arrays in place from the back, merge k sorted lists (pairwise merging or a heap), external sorting of data that does not fit in memory.

Template

Merge and top-down merge sort

def merge(a: list, b: list) -> list:
    """Merge two sorted lists; equal elements from a come first (stable)."""
    out = []
    i = j = 0
    while i < len(a) and j < len(b):
        if a[i] <= b[j]:  # <= keeps the sort stable
            out.append(a[i])
            i += 1
        else:
            out.append(b[j])
            j += 1
    out.extend(a[i:])
    out.extend(b[j:])
    return out


def merge_sort(a: list) -> list:
    if len(a) <= 1:
        return a[:]
    mid = len(a) // 2
    return merge(merge_sort(a[:mid]), merge_sort(a[mid:]))

Bottom-up merge sort (no recursion)

Merge runs of width 1, then 2, then 4, and so on:

def merge_sort_bottom_up(a: list) -> list:
    a = a[:]
    width = 1
    while width < len(a):
        for lo in range(0, len(a), 2 * width):
            mid, hi = lo + width, min(lo + 2 * width, len(a))
            a[lo:hi] = merge(a[lo:mid], a[mid:hi])
        width *= 2
    return a

Counting inversions

An inversion is a pair i < j with a[i] > a[j]. When right[j] wins a comparison, it is smaller than all len(left) - i remaining left elements:

def count_inversions(a: list[int]) -> int:
    def sort(xs: list[int]) -> tuple[list[int], int]:
        if len(xs) <= 1:
            return xs, 0
        mid = len(xs) // 2
        left, inv_left = sort(xs[:mid])
        right, inv_right = sort(xs[mid:])
        merged, inv = [], inv_left + inv_right
        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])
                j += 1
                inv += len(left) - i  # right[j] jumps over every remaining left element
        merged += left[i:] + right[j:]
        return merged, inv

    return sort(a)[1]

Count smaller numbers after self

For each position, count the later elements that are smaller. Sort indices by value so every element remembers where it came from. When a left-half element is placed, the right-half elements already placed before it are exactly the smaller ones that started to its right:

def count_smaller_after(nums: list[int]) -> list[int]:
    result = [0] * len(nums)

    def sort(idx: list[int]) -> list[int]:
        if len(idx) <= 1:
            return idx
        mid = len(idx) // 2
        left, right = sort(idx[:mid]), sort(idx[mid:])
        merged, j = [], 0
        for i in left:
            while j < len(right) and nums[right[j]] < nums[i]:
                merged.append(right[j])
                j += 1
            result[i] += j  # j right-half elements are smaller than nums[i]
            merged.append(i)
        merged.extend(right[j:])
        return merged

    sort(list(range(len(nums))))
    return result

Sorting a linked list

Find the middle with slow and fast pointers, cut the list in two, sort both halves, and merge by relinking nodes:

class ListNode:
    def __init__(self, val: int = 0, next: "ListNode | None" = None):
        self.val = val
        self.next = next


def sort_list(head: ListNode | None) -> ListNode | None:
    if head is None or head.next is None:
        return head
    slow, fast = head, head.next  # slow ends at the last node of the first half
    while fast and fast.next:
        slow, fast = slow.next, fast.next.next
    second, slow.next = slow.next, None  # cut the list in two
    a, b = sort_list(head), sort_list(second)
    dummy = tail = ListNode()
    while a and b:
        if a.val <= b.val:
            tail.next, a = a, a.next
        else:
            tail.next, b = b, b.next
        tail = tail.next
    tail.next = a or b  # attach whatever is left
    return dummy.next

Complexity

• Time: O(n log n) in the best, average and worst case. Counting inversions or smaller-after counts adds only O(1) per merge step.
• Space: O(n) for the merge buffers (the slicing versions above allocate O(n) per level, still O(n log n) total allocation but O(n) live at a time). The linked-list version needs no buffers, only O(log n) recursion stack; the bottom-up linked-list variant gets it down to O(1).
• Stable: yes, as long as ties take the left element first.

Common pitfalls

• Using < in the merge breaks stability, and in inversion counting it counts equal pairs as inversions.
• Forgetting the leftovers after the main merge loop.
• Wrong middle in linked lists. Starting fast at head instead of head.next leaves a two-node list unsplit and recurses forever.
• Off-by-one in the inversion count. Add len(left) - i (remaining left elements), not mid - i with mismatched indices.
• Integer overflow in languages with fixed-width integers: n = 10^5 elements can have about 5 * 10^9 inversions, so use 64-bit counters in C++ or Java.
• Losing original positions when a problem asks for per-element answers: sort indices, not values.

Interview variations

• Merge two sorted arrays in place when the first has free space at the end: fill from the back so nothing is overwritten.
• Merge k sorted lists: merge pairwise in rounds (O(N log k)) or keep the k front elements in a min-heap.
• Reverse pairs (i < j and a[i] > 2 * a[j]): before merging two sorted halves, count matching pairs with a two-pointer sweep, then merge normally.
• Count of range sums: merge sort over prefix sums, counting for each left prefix how many right prefixes fall in a window.
• Global versus local inversions, minimum adjacent swaps to sort: both reduce to inversion counting.
• External sort: sort chunks that fit in memory, write them out, then do a k-way merge with a heap.