the quicksort partition

Quicksort sorts by a different trick than merge sort: instead of dividing blindly down the middle and doing the clever work when combining, it does the clever work up front when dividing, and then has nothing to do when combining. The key operation is the partition: pick one element as the pivot, then rearrange the array so every element smaller than the pivot sits to its left and every larger element to its right. Now the pivot is in its final sorted position, and you recurse on the left part and the right part independently.

Here is the Lomuto partition in plain steps on [3,7,1,5 | pivot=4] (pivot chosen, say, as the last element in the usual version; here we use 4 for illustration): walk a pointer i across the array, keeping the invariant that everything left of a boundary is < pivot. Each element < pivot is swapped to just past the boundary; elements >= pivot are skipped. After one linear O(n) pass, the array is split into [< pivot][pivot][>= pivot] and the pivot index is returned. Quicksort then calls itself on the two sides. Because partition places the pivot correctly and the two sides are disjoint slices that are sorted independently, the array ends up sorted — there is no combine step at all.

When pivots split the array roughly in half, the recurrence is T(n) = 2 T(n/2) + O(n) = O(n log n), and in practice quicksort is often the fastest in-memory sort because partition is cache-friendly and in-place (only O(log n) stack space). But the honest caveat is the worst case: if every pivot is the smallest or largest element — for instance on already-sorted input with a naive last-element pivot — partition peels off just one element each time, giving T(n) = T(n-1) + O(n) = O(n^2). This is exactly why pivots are usually chosen randomly or by median-of-three, which makes the bad case astronomically unlikely.