Sorting Algorithms Runtime, Stability, and Use Cases Overview

Insertion sort — Best case

Runtime: O(n). Example: already sorted ascending, e.g., [1,2,3,4,5]; each insertion does 1 compare, 0 shifts.

Insertion sort — Worst case

Runtime: O(n^2). Example: reverse sorted, e.g., [5,4,3,2,1]; each new key shifts across the whole left side.

Insertion sort — Average case

Runtime: O(n^2). Example: random order, e.g., [3,1,4,2,5]; about n^2/4 shifts on average.

Selection sort — Best case

Runtime: O(n^2). Example: already sorted [1,2,3,4,5]; still scans remaining suffix each pass.

Selection sort — Worst case

Runtime: O(n^2). Example: reverse [5,4,3,2,1]; still does full scans and swaps.

Selection sort — Average case

Runtime: O(n^2). Example: random input; always ~n(n−1)/2 comparisons regardless of order.

Bubble sort — Best case (with early exit)

Runtime: O(n). Example: already sorted [1,2,3,4,5]; one pass, no swaps, loop stops early.

Bubble sort — Worst case

Runtime: O(n^2). Example: reverse [5,4,3,2,1]; many adjacent swaps each pass.

Bubble sort — Average case

Runtime: O(n^2). Example: random input; about half the pairs out of order.

Counting sort — Best case

Runtime: O(n + k). Example: small integer keys, e.g., values in {0,1,2,3}; single pass counting + prefix sums.

Counting sort — Worst case

Runtime: O(n + k). Example: still O(n+k); worst when k large relative to n (big count array).

Counting sort — Average case

Runtime: O(n + k). Example: random integers in a small fixed range; linear if k = O(n).

Radix sort — Best case

Runtime: O(d·(n + k)). Example: 32-bit ints with base 256 ⇒ d=4, k=256; 4 stable counting passes.

Radix sort — Worst case

Runtime: O(d·(n + k)). Example: same asymptotics; if d or k grows with n, time grows accordingly.

Radix sort — Average case

Runtime: O(d·(n + k)). Example: fixed-length digit strings; stable inner sort preserves prior digit order.

Bucket sort — Best case

Runtime: O(n + k). Example: n real numbers ~uniform in [0,1); evenly distributed buckets, tiny per-bucket sorts.

Bucket sort — Worst case

Runtime: O(n^2). Example: all values fall into one bucket (e.g., all 0.5); devolves to sorting one big bucket.

Bucket sort — Average case

Runtime: O(n + k). Example: iid uniform [0,1); expected small bucket sizes, insertion sort inside is cheap.

Binary search — Best case

Runtime: O(1). Example: target exactly at mid index on first check.

Binary search — Worst case

Runtime: O(log n). Example: target absent (e.g., search 7 in [1,3,5,9,11,13,15]); halves until interval empty.

Binary search — Average case

Runtime: O(log n). Example: random target position in a sorted array; expected ~log₂ n comparisons.

Insertion sort — Stability

Stable. Equal keys keep order because elements only shift right while scanning left.

Selection sort — Stability

Not stable (classic in-place). Selecting min and swapping can move equal keys past each other. (Stable variants exist but not the default.)

Bubble sort — Stability

Stable. Only adjacent swaps; equal elements are never swapped out of order.

Counting sort — Stability

Stable if implemented with cumulative counts and backward placement. (This stability is required for radix sort.)

Radix sort — Stability

Stable when each digit pass uses a stable sort (typically stable counting). LSD radix correctness relies on stability.

Bucket sort — Stability

Depends on bucket-sorting method. Using a stable sort per bucket makes it stable; using an unstable sort may break stability.