Quick Sort — Average vs Worst Case

Compare how pivot selection and data order affect the number of comparisons

Speed: 500ms
Active range
Pivot
Comparing
Swapping
Sorted
Average Case Shuffled Array

First-element pivot on random data — balanced partitions

Comparisons: 0
Press Step or Play to begin
Worst Case Reverse Sorted

First-element pivot on reverse-sorted data — maximally unbalanced

Comparisons: 0
Press Step or Play to begin

Big O Analysis — Why Does This Happen?

Best / Average Case

O(n log n)

When the pivot splits the array roughly in half each time, we get log n levels of recursion. Each level does n comparisons total across all partitions.

With 8 elements: log₂(8) = 3 levels × 8 ≈ ~16 comparisons.

Worst Case

O(n²)

When the pivot is always the smallest (or largest) element, one partition has n−1 elements and the other has 0. This gives n levels of recursion.

With 8 elements: 7+6+5+4+3+2+1 = 28 comparisons.

Key takeaway: Quick Sort's performance depends heavily on pivot choice. A reverse-sorted array with a first-element pivot triggers the worst case every time. To avoid this, use strategies like random pivot, median-of-three, or shuffle the array first.