Quicksort

Quicksort is a sorting algorithm that partitions an array around one item, the pivot, so that smaller items sit to its left and the rest to its right, and then sorts each side by calling itself. The partition leaves the pivot in its final place and needs no merge afterwards, and the choice of pivot decides everything else: whether the sort takes O(n log n) or O(n²) time, and how deep its stack of calls grows. The topic opens on the partitions of seven numbers, then walks through the Lomuto scheme one swap at a time. A gotcha shows a last-item pivot turning sorted input into the slow case, and a concept card keeps the stack shallow by recursing into the smaller side. The code card puts a random pivot and that loop together in three languages, and a comparison weighs Lomuto's scheme against Hoare's on shuffled, sorted and all-equal input. The topic closes on quickselect, which partitions to find the k-th smallest item in expected linear time, and an exercise that uses it to find a median.