08. Sorting Algorithms

Sorting is the most studied problem in computer science. Not because sorting itself is hard — but because the techniques (divide-and-conquer, partitioning, merging) appear everywhere else. Understanding merge sort teaches you divide-and-conquer. Understanding quicksort teaches you partitioning. Understanding when O(n log n) is optimal teaches you lower bounds.

Why O(n log n)?

Any comparison-based sort must be Ω(n log n) in the worst case. There are n! possible orderings, and each comparison eliminates at most half. You need at least log₂(n!) ≈ n log n comparisons to distinguish all orderings.

This means: merge sort and quicksort (average) are optimal. You can't do better with comparisons alone.

Merge Sort

Divide the array in half, sort each half recursively, merge the two sorted halves.

func mergeSort(nums []int) []int {
    if len(nums) <= 1 {
        return nums
    }
    mid := len(nums) / 2
    left := mergeSort(nums[:mid])
    right := mergeSort(nums[mid:])
    return merge(left, right)
}

func merge(a, b []int) []int {
    result := make([]int, 0, len(a)+len(b))
    i, j := 0, 0
    for i < len(a) && j < len(b) {
        if a[i] <= b[j] {
            result = append(result, a[i])
            i++
        } else {
            result = append(result, b[j])
            j++
        }
    }
    result = append(result, a[i:]...)
    result = append(result, b[j:]...)
    return result
}

Time: O(n log n) always — guaranteed, no worst case. Space: O(n) — needs a temporary array for merging. Stable: Yes — equal elements keep their original order.

Merge sort is the go-to when you need guaranteed O(n log n) or stability. It's also the basis for external sorting (sorting data that doesn't fit in memory).

Quicksort

Pick a pivot, partition the array so everything smaller is on the left and everything larger is on the right, then recurse on each side.

func quickSort(nums []int, lo, hi int) {
    if lo >= hi {
        return
    }
    pivot := partition(nums, lo, hi)
    quickSort(nums, lo, pivot-1)
    quickSort(nums, pivot+1, hi)
}

func partition(nums []int, lo, hi int) int {
    pivot := nums[hi] // choose last element as pivot
    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
}

Time: O(n log n) average, O(n²) worst case (already sorted + bad pivot). Space: O(log n) — recursion stack only, sorts in-place. Stable: No — partitioning can reorder equal elements.

Quicksort is faster in practice than merge sort (better cache behavior, no extra allocation) despite the worse worst case. Most standard library sorts use a quicksort variant.

Partition: The Key Insight

The partition step is useful beyond sorting. It places the pivot in its final sorted position in O(n). This enables:

• Quickselect — find the kth smallest element in O(n) average without fully sorting
• Dutch National Flag — three-way partition (less, equal, greater) for arrays with many duplicates

Comparison

Simple Sorts (O(n²))

These are slow but useful to understand:

Insertion sort — build the sorted portion one element at a time. Fast on nearly-sorted data (O(n) best case). Used as the base case in hybrid sorts.

func insertionSort(nums []int) {
    for i := 1; i < len(nums); i++ {
        key := nums[i]
        j := i - 1
        for j >= 0 && nums[j] > key {
            nums[j+1] = nums[j]
            j--
        }
        nums[j+1] = key
    }
}

Selection sort — find the minimum, swap it to the front, repeat. Always O(n²), no practical use except minimal swaps.

Go's sort.Slice

In practice, use the standard library:

import "sort"

nums := []int{5, 2, 8, 1, 9}
sort.Ints(nums) // [1, 2, 5, 8, 9]

// Custom comparator
sort.Slice(nums, func(i, j int) bool {
    return nums[i] > nums[j] // descending
})

Go's sort.Slice uses a hybrid algorithm (introsort: quicksort + heapsort fallback + insertion sort for small arrays). You don't implement sorting in production — but you need to understand it for interviews and for problems that use sorting as a preprocessing step.

Sorting as a Preprocessing Step

Many problems become easier after sorting:

• Two Sum (sorted) → two pointers, O(n)
• Merge intervals → sort by start, then linear scan
• Meeting rooms → sort by start/end time
• Kth largest → sort and index (or quickselect for O(n))
• Anagram grouping → sort each word as a key

Practice Problems

Key Takeaways

• Comparison-based sorting has a lower bound of O(n log n) — merge sort and quicksort are optimal
• Merge sort: guaranteed O(n log n), stable, but uses O(n) extra space
• Quicksort: O(n log n) average, in-place, faster in practice, but O(n²) worst case
• Partition is the key operation — it places one element in its final position in O(n)
• Insertion sort is O(n) on nearly-sorted data — used as base case in hybrid sorts
• In practice, use sort.Slice. In interviews, know how merge sort and quicksort work.
• Sorting is often a preprocessing step that enables simpler algorithms