Phase 4Days 18-21

Sorting Techniques

Implement the classic sorts, understand invariants, and use custom comparators fluently

Phase Goal

Know how sorting really works and wield sorting as a preprocessing weapon.

Progress

Day 18: Quadratic sorts & the idea of an invariant

The invariant: the prefix is sorted and holds the smallest elementsSelecting the minimum of the unsorted suffix each passO(n^2) comparisons, O(n) swaps; not stableDry run on 5 elements tracking the boundary

Adjacent swaps bubbling the max to the end each passEarly-exit when a pass makes no swaps (best case O(n))Stability and why equal elements keep their orderWorst case O(n^2)

Inserting each new element into the sorted prefixWhy it is fast on nearly-sorted data (O(n) best case)Stable and in-place; the shifting costWhere library sorts fall back to insertion sort for tiny ranges

Choose one core problem from LeetCode, Codeforces, AtCoder, or CSES after checking its prerequisites; hide its technique labelSpend 10–20 minutes retrieving one earlier mechanism and one earlier bug before new work; prioritize weak prerequisitesUse a five-task bank: guided warm-up, core, changed constraint, delayed recall, optional stretch; attempt one or two, not all five on a timerBefore a solution, produce a trace or brute-force plan; when stuck take one hint, act on it, then reassessRecord help used, the failing input, the corrected reasoning, and a next review date; start around 1/3/7/14/30 days and adaptReserve a weekly mixed review; after foundation readiness add a short virtual contest and upsolve one task with known prerequisitesProve progress through a delayed blank-editor reconstruction and a changed problem; a same-day quiz is supporting evidence only

Day 19: Merge sort & divide and conquer

Split in half, sort each half, merge two sorted halvesWhy recursion (Phase 3) is the natural fitThe merge step: two pointers walking both halvesO(n log n) time, O(n) extra space

The recursive split with mid = l + (r - l) / 2Writing a correct, stable merge into a temp bufferCopying back and the index-bookkeeping trapsVerifying with a hand trace on 6 elements

What an inversion is and why it measures unsortednessCounting inversions during the merge step for freeReverse pairs as a merge-sort variantWhy brute force is O(n^2) and this is O(n log n)

Day 20: Quick sort & quickselect

Choosing a pivot and partitioning around itLomuto versus Hoare partition schemesIn-place, not stable; O(n log n) average, O(n^2) worstWhy a bad pivot on sorted input degrades it

Recursing on the two partitionsRandomized or median-of-three pivot to dodge the worst caseRecursion depth considerationsComparing quick versus merge in practice

Partition once, recurse into only the side containing kAverage O(n), worst O(n^2)Finding the kth smallest or largestWhen quickselect beats sorting or a heap

Day 21: Non-comparison sorts & sorting in practice

Counting sort for a small integer range in O(n + k)Why comparison sorts cannot beat O(n log n) but these canRadix sort digit by digit and its stability requirementBucket sort intuition for uniform data

std::sort is introsort: O(n log n) guaranteedSorting structs by multiple keys with a comparatorSorting indices by their values with a capturing lambdastable_sort versus sort and when the order of equals matters

Many problems become easy once sorted (pairs, greedy, two-pointer)Coordinate compression: map values to ranksSorting plus binary search combosRecognizing when sorting is the unlock

Phase Complete!

After this phase, you'll be able to:

Quadratic sorts & the idea of an invariant
Merge sort & divide and conquer
Quick sort & quickselect
Non-comparison sorts & sorting in practice

After Phase 4, explain a core invariant, reconstruct a solution after a delay, diagnose a bug, and solve one unlabelled variation. Repair a failed prerequisite before advancing; record help separately from independent work.

Back to all phases

Sorting Techniques

Phase Goal

Day 18: Quadratic sorts & the idea of an invariant

Selection sort

Bubble sort

Insertion sort

Practice, delayed recall, and independent transfer

Day 19: Merge sort & divide and conquer

The divide-and-conquer idea

Implementing merge sort

Counting inversions

Practice, delayed recall, and independent transfer

Day 20: Quick sort & quickselect

Partitioning

Quick sort assembly

Quickselect — kth element without a full sort

Practice, delayed recall, and independent transfer

Day 21: Non-comparison sorts & sorting in practice

Counting & radix sort

std::sort and custom comparators (mastery)

Sorting as a preprocessing weapon

Practice, delayed recall, and independent transfer

Phase Complete!