Step 1 of 7 · Understand
Choose a value, not a midpoint
Goal: Define what partition must produce.
Start with [7,9,12,6,3,1,10,2]. Choose the first value, 7, as the pivot. We want values ≤ 7 on the left and values > 7 on the right, with the chosen pivot between them.
This is partitioning. It does not promise that either side is sorted. Unlike Merge Sort, the split is based on value comparisons, not a fixed midpoint. Its size depends on the chosen pivot and the data.
Our convention sends other values equal to the pivot to the left. Other valid partition schemes use different rules; do not mix their boundaries or trace steps with this one.
Remember: Partition fixes a pivot position but leaves both sides to be sorted.