Understanding Quicksort's Partition Step

Quicksort picks a pivot, partitions the array so smaller elements go left and larger go right, then recursively sorts both halves. Average time is

, worst case

when the pivot is always the smallest or largest. Choosing a random pivot avoids the worst case in practice.