λDSA Learning Hubpart of DSA Atlas

Sorting

Intermediate~3h · 7 lessons10 practice problems

From bubble to quick sort with side-by-side animations: how each algorithm moves data, when O(n²) is fine, why O(n log n) is the wall, and how counting sort tunnels under it.

0 of 7 lessons checked off

Introduction

What it is

  • Sorting rearranges data into order. The comparison sorts (bubble, selection, insertion, merge, quick, heap) work by comparing pairs; the counting family (counting, radix, bucket) exploits structure in the keys to skip comparisons entirely.
  • Two labels matter beyond speed: stable (equal elements keep their original relative order) and in-place (O(1) or O(log n) extra memory).

Why it matters

  • Sortedness is a precondition machine: binary search, two pointers, merging intervals, greedy scheduling, and deduplication all switch on after one O(n log n) sort.
  • Interviewers rarely ask you to implement quicksort cold — they ask WHICH sort fits a scenario, whether stability matters, and why your 'faster' idea can't beat Ω(n log n) comparisons.

How it works

  • O(n²) sorts grow a sorted region one element per pass (selection picks the min; insertion slides the next element home; bubble floats the max up).
  • Merge sort splits and re-zips; quick sort partitions around a pivot so each element reaches its final home; heap sort repeatedly extracts the max from a heap.
  • Counting sort tallies occurrences of each key value; radix applies it digit by digit — O(n + k), no comparisons.

Where it's used

  • Python's built-in sort (Timsort) is a merge/insertion hybrid tuned for real data with pre-sorted runs — the practical answer to 'which sort should I use?' is almost always 'the built-in'.
  • Databases external-merge-sort data too big for memory; graphics pipelines radix-sort draw calls; log processors bucket by time.

In interviews

  • Sort-then-sweep problems (merge intervals, meeting rooms), k-th element via quickselect, 'sort colors' (Dutch flag partitioning), custom comparator questions, and stability scenarios.
Analogy: Sorting a hand of cards: insertion sort is how humans actually do it (slide each new card into place). Merge sort is two friends each sorting half the deck and zipping the halves. Quick sort is announcing 'everything smaller than this card to my left' and repeating inside each side.

Interactive diagram

Halves are sorted independently, then zipped by repeatedly taking the smaller front element.

Unsorted input

Merge sort splits the array in half until pieces have one element, then merges sorted halves back together.

Lessons in this topic

Check off lessons as you go — your progress is saved in this browser.

  1. Bubble, selection, insertion sort

    The O(n²) trio: mechanics, best cases, and when they're actually the right tool.

    35 min
  2. Merge sort

    Divide & conquer, the O(n) merge, guaranteed O(n log n), stability.

    25 min
  3. Quick sort

    Partitioning, pivot choice, average vs worst case, quickselect.

    30 min
  4. Heap sort (overview)

    Heapify + repeated extract-max: O(n log n), in-place, not stable.

    15 min
  5. Counting, radix, bucket sort

    Beating the comparison bound when keys are small integers or uniform.

    30 min
  6. Stability and in-place-ness

    Which sorts preserve ties, which need buffers, and when each property matters.

    15 min
  7. What Python actually does (Timsort)

    Runs, galloping, and why sorted(data) is the right production answer.

    15 min

Operations

Bubble sort

Compare neighbours, swap when out of order; the largest value bubbles to the end each pass. Early-exit when a pass makes no swaps.

Unsorted input

Bubble sort repeatedly compares neighbours and swaps them when out of order. The largest value 'bubbles' to the end of each pass.

def bubble_sort(nums: list[int]) -> None:    """In place, stable. O(n^2) worst, O(n) best (already sorted)."""    n = len(nums)    for end in range(n - 1, 0, -1):        swapped = False        for i in range(end):            if nums[i] > nums[i + 1]:                nums[i], nums[i + 1] = nums[i + 1], nums[i]                swapped = True        if not swapped:        # a clean pass means fully sorted            break
Time: Best O(n) · average/worst O(n²)Space: O(1), stable

Edge cases

  • Already-sorted input: the swapped flag exits after one pass.
  • All-equal elements: no swaps ever happen (stability preserved).
  • Single element or empty: the outer range is empty — safe.

Common mistakes

  • Omitting the early-exit flag, turning the best case back into O(n²).
  • Looping i to n−1 instead of end, re-scanning the already-settled suffix.

Selection sort

Scan the unsorted region for its minimum and swap it to the front. Exactly n−1 swaps — minimal writes, maximal comparisons.

Unsorted input

Selection sort finds the minimum of the unsorted region and swaps it to the front — one guaranteed placement per pass.

def selection_sort(nums: list[int]) -> None:    """In place, NOT stable. Always Θ(n^2) comparisons, ≤ n-1 swaps."""    n = len(nums)    for i in range(n - 1):        smallest = i        for j in range(i + 1, n):            if nums[j] < nums[smallest]:                smallest = j        if smallest != i:            nums[i], nums[smallest] = nums[smallest], nums[i]
Time: Θ(n²) in every case — no adaptive best caseSpace: O(1), not stable

Edge cases

  • Sorted input still costs Θ(n²) comparisons — selection can't detect it.
  • The long-range swap is what breaks stability: equal elements can leapfrog.
  • Duplicate minimums: the first one found is taken.

Common mistakes

  • Swapping inside the inner loop (that's bubble-ish and wrong for the swap-count guarantee).
  • Claiming selection sort is stable — the swap teleports elements over equals.

Insertion sort

Grow a sorted prefix; each new element walks left to its slot. Nearly-sorted input walks almost nowhere — the adaptive O(n) best case.

Unsorted input

Insertion sort grows a sorted prefix. Each new value walks left until it finds its slot — like sorting cards in your hand.

def insertion_sort(nums: list[int]) -> None:    """In place, stable, adaptive. O(n^2) worst, O(n) nearly-sorted."""    for i in range(1, len(nums)):        key = nums[i]        j = i - 1        while j >= 0 and nums[j] > key:            nums[j + 1] = nums[j]      # shift right            j -= 1        nums[j + 1] = key
Time: Best O(n) · worst O(n²) (reverse-sorted)Space: O(1), stable

Edge cases

  • Nearly-sorted data: each key shifts O(1) — this is why Timsort uses insertion for small runs.
  • Reverse-sorted data: every key walks to index 0 — the true worst case.
  • Strict > (not >=) in the walk keeps equal elements stable.

Common mistakes

  • Using >= in the comparison, silently breaking stability.
  • Swapping at every step instead of shifting (3× the writes).

Merge sort

Recursively sort halves, then merge in O(n). The only mainstream sort with a guaranteed O(n log n) AND stability — at the price of O(n) buffer.

Unsorted input

Merge sort splits the array in half until pieces have one element, then merges sorted halves back together.

def merge_sort(nums: list[int]) -> list[int]:    """Stable, guaranteed O(n log n); O(n) extra space."""    if len(nums) <= 1:        return nums    mid = len(nums) // 2    left = merge_sort(nums[:mid])    right = merge_sort(nums[mid:])    merged: list[int] = []    i = j = 0    while i < len(left) and j < len(right):        if left[i] <= right[j]:          # <= preserves stability            merged.append(left[i]); i += 1        else:            merged.append(right[j]); j += 1    merged.extend(left[i:])    merged.extend(right[j:])    return merged
Time: Θ(n log n) — best, average, and worstSpace: O(n) buffers + O(log n) stack

Edge cases

  • Leftover run after one side empties — the two extend calls.
  • <= vs < during merge decides stability.
  • Linked-list merge sort achieves O(1) extra space — a classic follow-up.

Common mistakes

  • Forgetting the leftovers, silently dropping elements.
  • Re-slicing inside the merge loop (hidden O(n) per step).

Quick sort

Partition around a pivot — smaller left, larger right — placing the pivot at its final index; recurse on both sides. Fast constants, fragile worst case.

Unsorted input

Quick sort picks a pivot, partitions smaller values to its left and larger to its right, then recurses on each side.

import randomdef quick_sort(nums: list[int], lo: int = 0, hi: int | None = None) -> None:    """In place, average O(n log n), worst O(n^2). Not stable."""    if hi is None:        hi = len(nums) - 1    if lo >= hi:        return    # random pivot defends against sorted/adversarial input    r = random.randint(lo, hi)    nums[r], nums[hi] = nums[hi], nums[r]    pivot = nums[hi]    i = lo - 1    for j in range(lo, hi):            # Lomuto partition        if nums[j] <= pivot:            i += 1            nums[i], nums[j] = nums[j], nums[i]    nums[i + 1], nums[hi] = nums[hi], nums[i + 1]    quick_sort(nums, lo, i)            # left of pivot    quick_sort(nums, i + 2, hi)        # right of pivot
Time: Average O(n log n) · worst O(n²) without pivot randomisationSpace: O(log n) average stack, in place

Edge cases

  • Sorted input + last-element pivot = the O(n²) worst case; randomisation fixes it.
  • Many duplicates degrade Lomuto — 3-way (Dutch flag) partitioning is the cure.
  • Recursing on [lo, i] and [i+2, hi] skips the settled pivot.

Common mistakes

  • Always picking the first/last pivot and testing only random arrays — the worst case hides until production.
  • Recursing on ranges that include the pivot, causing infinite recursion on duplicates.

Counting sort (beating the comparison bound)

When keys are small integers, tally each value and rebuild — no comparisons, O(n + k). The prefix-sum placement keeps it stable for radix sort.

Counting sort (beating the comparison bound)
def counting_sort(nums: list[int], max_value: int) -> list[int]:    """Stable counting sort for 0..max_value keys. O(n + k)."""    counts = [0] * (max_value + 1)    for x in nums:                     # tally        counts[x] += 1    for v in range(1, max_value + 1):  # prefix sums: end position of each value        counts[v] += counts[v - 1]    out = [0] * len(nums)    for x in reversed(nums):           # backwards pass keeps ties stable        counts[x] -= 1        out[counts[x]] = x    return out
Time: O(n + k), k = key rangeSpace: O(n + k), stable

Edge cases

  • k much larger than n (e.g. keys up to 10⁹) makes the counts array the bottleneck — counting sort is wrong there.
  • Negative keys need an offset shift first.
  • The reversed pass is what makes radix sort possible on top.

Common mistakes

  • Using it as a general-purpose sort regardless of key range.
  • Forward placement pass, which silently breaks stability (and thus radix).

Complexity analysis

OperationBestAverageWorstSpace
Bubble sortO(n)O(n²)O(n²)O(1) · stable
Selection sortO(n²)O(n²)O(n²)O(1) · unstable
Insertion sortO(n)O(n²)O(n²)O(1) · stable
Merge sortO(n log n)O(n log n)O(n log n)O(n) · stable
Quick sortO(n log n)O(n log n)O(n²)O(log n) · unstable
Heap sortO(n log n)O(n log n)O(n log n)O(1) · unstable
Counting sortO(n + k)O(n + k)O(n + k)O(n + k) · stable
Radix sort (d digits)O(d·(n + b))O(d·(n + b))O(d·(n + b))O(n + b) · stable
Timsort (Python's sorted)O(n)O(n log n)O(n log n)O(n) · stable

The table interviewers expect you to reproduce from memory. Stability and space are as quotable as time.

Python implementation

Production-quality code with type hints, validation, and docstrings.

Quickselect: k-th smallest in average O(n) (sorting's best spin-off)
import randomdef quickselect(nums: list[int], k: int) -> int:    """Return the k-th smallest (1-indexed) element.    Average O(n): each round keeps ONE side, unlike quicksort's two."""    if not 1 <= k <= len(nums):        raise ValueError("k out of range")    lo, hi = 0, len(nums) - 1    target = k - 1                       # index in sorted order    while True:        if lo == hi:            return nums[lo]        # randomised Lomuto partition        r = random.randint(lo, hi)        nums[r], nums[hi] = nums[hi], nums[r]        pivot = nums[hi]

What interviewers expect you to know

What interviewers expect you to know

  • The full complexity/stability table above, cold.
  • Comparison sorts cannot beat Ω(n log n): n! orderings need log₂(n!) ≈ n log n bits of comparisons — cite it when asked 'can you do better?'.
  • Stability's practical meaning: sort by amount, then stably by date → grouped by date with amounts still ordered inside.
  • Quicksort vs merge sort trade-off: cache-friendly speed and O(log n) space vs guaranteed bound and stability.

Scenario questions to rehearse

  • "1M records, nearly sorted?" — insertion sort or Timsort (which detects runs): near O(n).
  • "Sort 10⁹ integers, values 0–255?" — counting sort: O(n + 256), no comparisons.
  • "Guaranteed latency, no O(n²) tail risk?" — merge or heap sort, never plain quicksort.
  • "K-th largest without full sort?" — quickselect average O(n), or a size-k heap at O(n log k).

How to answer 'which sort?'

  • Ask three questions out loud: how big? what are the keys? does stability matter? The answer usually falls out.
  • In code, call sorted() — then say what algorithm you'd reach for if you couldn't, and why.

Common mistakes

Quoting quicksort as O(n log n), full stop

That's the average. Worst case is O(n²) on adversarial/sorted input with naive pivots — say both, and say 'randomised pivot' as the fix.

Believing selection sort is stable

The long-distance swap jumps over equal elements. Bubble and insertion are the stable O(n²) sorts.

Merge without the leftovers

When one run empties, the other's remainder must be appended — dropping it loses data on every uneven merge.

Counting sort with huge key ranges

O(n + k) is a trap when k = 10⁹: the counts array alone is 4 GB. Check the key range before proposing it.

Re-sorting inside a loop

sorted() inside a per-element loop makes an O(n² log n) accident. Sort once, then sweep.

Ignoring the built-in

Implementing quicksort when the task allowed sorted() wastes interview minutes. Use the tool; explain the internals only when asked.

Practice problems

Hand-picked from the 355-problem DSA Atlas. Reveal hints and solutions progressively; mark and bookmark as you solve.

Easy (2)

Medium (6)

Hard (2)

Topic quiz

6 questions across concepts, code output, complexity, and scenarios. Answer all, then submit for explanations.

  1. Concept1. Which sorts are stable?
  2. Scenario2. Input is a 10⁶-element array that's already 99% sorted. Which algorithm exploits this best?
  3. Complexity3. Why can't any comparison-based sort beat O(n log n) in the worst case?
  4. Code output4. One Lomuto partition of [3, 8, 2, 5, 9, 4] with pivot 4 (last element) leaves the array as…
  5. Scenario5. You must sort 5 million 6-digit order IDs. The interviewer says 'faster than n log n'. What do you propose?
  6. Concept6. Merge sort on linked lists is attractive because…
0 of 6 answered

Frequently asked questions

Which sorting algorithm should I say Python uses?

Timsort: a stable merge/insertion hybrid that finds pre-sorted runs, merges them adaptively, and hits O(n) on sorted data, O(n log n) worst case. It's used by Python and (for objects) Java.

Do I ever need to hand-write quicksort in an interview?

Occasionally at the 'implement partition' level — and quickselect (built on partition) is genuinely common. Practice the Lomuto partition until it's mechanical; the rest is recursion.

When is an O(n²) sort actually the right choice?

Tiny inputs (n ≲ 32, where constants beat asymptotics — Timsort itself switches to insertion sort), nearly-sorted data (insertion is ~O(n)), or write-limited hardware (selection sort's n−1 swaps).

Summary & cheat sheet

Key takeaways

  • Learn the table: time × space × stability for all nine algorithms.
  • Ω(n log n) binds comparison sorts; counting/radix tunnel under it when keys are structured.
  • Insertion = adaptive and stable; merge = guaranteed and stable; quick = fastest average, needs randomisation; heap = guaranteed and in-place.
  • Partition once → pivot settled → quickselect finds k-th in O(n) average.
  • In practice: sorted() — and know why.

Formulas & cheat sheet

  • Comparison lower bound: log₂(n!) = Θ(n log n)
  • Merge sort: T(n) = 2T(n/2) + Θ(n) = Θ(n log n)
  • Quickselect: n + n/2 + n/4 + … = O(n) expected
  • Radix: O(d · (n + b)) for d digits in base b

Interview checklist

  • I can animate each algorithm on paper for a 5-element array.
  • I can reproduce the complexity/stability table from memory.
  • I can implement Lomuto partition and quickselect.
  • I can match five scenario prompts to the right algorithm.