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 , just like merge sort. Each level does work, giving average time.
But in the worst case (always picking the smallest or largest element as pivot), the tree has height , giving time. Randomization keeps the average case .