What is the worst-case cost for Quicksort's partition step?
\Theta(n)\Theta(n^2)\Theta(\log n)\Theta(n \log n)Partition moves indices inwards until the meet.
Each step either swaps or moves indices.
No record can swap more than once, and the total number of index moves can only be the length of the partition.