Randomized Quicksort

Random pivot · in-place partition · recursion · live comparison count

Expected: O(n log n)

Best: O(n log n)

Worst: O(n²) (prob→0)

Space: O(log n)

Type: Las Vegas

Speedslow fast

step / 0

comparisons

swaps

recursion depth

≈1.39·n·log₂n (predicted)

Unsorted

Active subarray

Random pivot

Comparing

Swapping

≤ pivot / sorted

What's happening

            Press Start for the full animation, or Step to advance one move.
            Try Sorted input — randomization keeps it fast (no O(n²) blow-up).
        

Case	Time	Why
Best	O(n log n)	balanced partitions
Expected (any input)	O(n log n)	~1.39 n log₂ n comparisons; random pivot
Worst (theoretical)	O(n²)	unlucky pivot streak; probability → 0
Space	O(log n)	recursion stack (expected)
Stable	No	partition can reorder equal keys
Correctness	Always	Las Vegas: only runtime is random

Randomized Quicksort

What's happening

Operation log