Logarithms in Quicksort (Average case)

Quicksort picks a pivot, partitions the array around it, then recursively sorts each partition. In the average case, the pivot splits the array roughly in half.

If partitions are balanced, the recursion tree has height $O(\log n)$, just like merge sort. Each level does $O(n)$ work, giving $O(n \log n)$ average time.

But in the worst case (always picking the smallest or largest element as pivot), the tree has height $O(n)$, giving $O(n^2)$ time. Randomization keeps the average case $O(n \log n)$.