Sorting, Selection & Divide-and-Conquer

Why this module exists

Sorting is more than ordering data. It powers selection, inversion counting, interval logic, and many divide-and-conquer tricks. If you know how partition and merge behave, you can solve problems that do not look like sorting.

Quicksort in one page

Quicksort repeatedly partitions around a pivot.

• Partition: all values < pivot to the left, > pivot to the right
• Recurse: sort left and right halves
• Average time: O(n log n)
• Worst case: O(n^2) without good pivot choice

A minimal partition (Lomuto) looks like this:

func partition(nums []int, lo, hi int) int {
    pivot := nums[hi]
    i := lo
    for j := lo; j < hi; j++ {
        if nums[j] < pivot {
            nums[i], nums[j] = nums[j], nums[i]
            i++
        }
    }
    nums[i], nums[hi] = nums[hi], nums[i]
    return i
}

Tip: randomize the pivot (or shuffle the array) to avoid worst-case inputs.

Quickselect (k-th order statistic)

Quickselect is quicksort where you only recurse into one side.

Steps for 1-indexed k:

1. Partition
2. If pivot index == k-1, done
3. Recurse into the half that contains k

Average time is O(n), because each partition discards ~half the array.

Merge sort as a counting engine

Merge sort splits the array, sorts each half, then merges. During merge, you can count cross-half events, like inversions:

• An inversion is a pair (i, j) with i < j and a[i] > a[j]
• While merging, if left[i] > right[j], then every remaining element in left also forms an inversion with right[j]

That is the key trick for inversion counting, pair counting, and similar tasks.

Divide-and-conquer template

1. Base case (size 0/1)
2. Split input
3. Recurse on subproblems
4. Combine results

Most of the value is in the combine step. Examples beyond sorting:

• Closest pair of points (geometry)
• Matrix chain order (interval DP)
• Counting pairs with constraints

What you will build

• Quickselect for the k-th smallest element.
• Count inversions during a merge.