Sorting Basics: Stability and the Simple O(n^2) Sorts

You will rarely be asked to hand-write a quadratic sort, but interviews constantly assume the vocabulary around sorting: which sorts are stable, which are in place, why nothing comparison-based beats O(n log n), and which algorithm fits a nearly sorted input. This article covers that vocabulary and the three simple O(n^2) sorts, then compares every common sort in one table.

Intuition

Key properties to name when discussing any sort:

• Stable: records with equal keys keep their original relative order. Stability is what lets you sort by a secondary key first and the primary key second and get a correct multi-key order.
• In place: uses O(1) (or O(log n)) extra memory.
• Adaptive: runs faster when the input is already partly sorted.
• Comparison-based: learns about the order only by comparing pairs of elements.

Any comparison sort needs Ω(n log n) comparisons in the worst case. A run of the algorithm is a binary decision tree whose leaves must distinguish all n! orderings, so its height is at least log2(n!), which is about n log2 n. Counting, radix and bucket sort beat this bound only because they look at the values themselves instead of comparing.

The three simple sorts each grow a sorted region one element at a time:

• Selection sort finds the minimum of the unsorted part and swaps it to the front. Always O(n^2) comparisons, but at most n - 1 swaps.
• Bubble sort repeatedly swaps adjacent out-of-order pairs; after pass i the largest i elements are in their final places.
• Insertion sort takes the next element and shifts it left into its place within the sorted prefix, like sorting a hand of cards.

When to use it in interviews / OAs

• Small or nearly sorted inputs: insertion sort runs in O(n + inversions), so it is O(n) on sorted data and O(n * k) when every element is at most k positions from its final spot. Production sorts switch to insertion sort for tiny subarrays.
• Expensive writes: selection sort performs the fewest swaps of the simple sorts.
• Linked lists: insertion sort works naturally on a linked list (no shifting needed), and is a common warm-up question.
• Counting operations: the number of swaps bubble sort performs equals the number of inversions; the minimum number of arbitrary swaps to sort is tied to the cycles that selection-style swapping resolves.
• Stability questions: "sort by name, then stably by age" relies on a stable sort; Python's sorted and list.sort are stable.

Template

def selection_sort(a: list) -> None:
    n = len(a)
    for i in range(n - 1):
        smallest = i
        for j in range(i + 1, n):
            if a[j] < a[smallest]:
                smallest = j
        a[i], a[smallest] = a[smallest], a[i]  # one swap per position

The long-distance swap is what breaks stability. Sorting [(2, "a"), (2, "b"), (1, "c")] by the number swaps (2, "a") to the back, past (2, "b").

def bubble_sort(a: list) -> None:
    n = len(a)
    for end in range(n - 1, 0, -1):
        swapped = False
        for i in range(end):
            if a[i] > a[i + 1]:  # strict comparison: equal items never swap (stable)
                a[i], a[i + 1] = a[i + 1], a[i]
                swapped = True
        if not swapped:  # no swaps means already sorted: O(n) best case
            break

def insertion_sort(a: list) -> None:
    for i in range(1, len(a)):
        key = a[i]
        j = i - 1
        while j >= 0 and a[j] > key:  # strict comparison keeps it stable
            a[j + 1] = a[j]  # shift larger elements one step right
            j -= 1
        a[j + 1] = key

Finding the insertion point with binary search (bisect.insort in Python) reduces comparisons to O(n log n), but shifting elements is still O(n^2) in the worst case.

A common follow-up: the minimum number of swaps (of any two elements) needed to sort an array of distinct values. Each element should move to the position of its rank; those moves form cycles, and a cycle of length L takes L - 1 swaps:

def min_swaps_to_sort(nums: list[int]) -> int:
    """Minimum swaps of arbitrary pairs to sort distinct values."""
    order = sorted(range(len(nums)), key=nums.__getitem__)  # index of the k-th smallest
    seen = [False] * len(nums)
    swaps = 0
    for start in range(len(nums)):
        length, i = 0, start
        while not seen[i]:  # walk one cycle of the permutation
            seen[i] = True
            i = order[i]
            length += 1
        swaps += max(0, length - 1)
    return swaps

Complexity

Algorithm	Best	Average	Worst	Extra space	Stable
Selection sort	O(n^2)	O(n^2)	O(n^2)	O(1)	No
Bubble sort (early exit)	O(n)	O(n^2)	O(n^2)	O(1)	Yes
Insertion sort	O(n)	O(n^2)	O(n^2)	O(1)	Yes
Merge sort	O(n log n)	O(n log n)	O(n log n)	O(n)	Yes
Quicksort (random pivot)	O(n log n)	O(n log n)	O(n^2)	O(log n) stack	No
Heap sort	O(n log n)	O(n log n)	O(n log n)	O(1)	No
Counting sort (values in a range of size k)	O(n + k)	O(n + k)	O(n + k)	O(n + k)	Yes
LSD radix sort (d digits, base b)	O(d(n + b))	O(d(n + b))	O(d(n + b))	O(n + b)	Yes
Bucket sort (uniform data)	O(n)	O(n)	O(n^2)	O(n)	Yes, with a stable inner sort
Timsort (Python, Java objects)	O(n)	O(n log n)	O(n log n)	O(n)	Yes

min_swaps_to_sort is O(n log n) because of the sort that computes ranks; the cycle walk is O(n).

Common pitfalls

• Using an O(n^2) sort when n is 10^5: that is 10^10 operations. Hand-written sorts in interviews should be merge sort, quicksort or heap sort unless the input is tiny or nearly sorted.
• Writing >= instead of > in bubble or insertion sort: equal elements get swapped and the sort is no longer stable.
• Forgetting the early-exit flag in bubble sort, which removes its O(n) best case.
• Calling selection sort stable. The array version with swaps is not.
• Off-by-one errors in the inner loops: bubble sort's pass i only needs to look at the first n - i elements.

Interview variations

• Insertion sort on a linked list: keep a dummy head for the sorted list and splice each node into place.
• Count the swaps bubble sort would make: that is the inversion count; compute it in O(n log n) with merge sort.
• Minimum adjacent swaps to sort: also the inversion count.
• Minimum arbitrary swaps to sort: n minus the number of cycles, as above.
• k-sorted array (each element at most k from its place): insertion sort in O(n * k), or a min-heap of size k + 1 in O(n log k).
• Multi-key sorting with stability: sort by the secondary key, then stably by the primary key, or use a tuple key in one pass.