Analysis of quicksort
partitionfunction is always either the smallest or the largest element in the -element subarray. Then one of the partitions will contain no elements and the other partition will contain elements—all but the pivot. So the recursive calls will be on subarrays of sizes 0 and .
Worst-case running time
Best-case running time
Average-case running time
nnodes, and so the partitioning time for every level is at most . Altogether, there are levels, and so the total partitioning time is . Now, there's a mathematical fact that
partitionfunction assumes that the pivot is in the rightmost position of the subarray. No problem—just swap the element that you chose as the pivot with the rightmost element, and then partition as before. Unless your enemy knows how you choose random locations in the subarray, you win!