What is the time complexity of quick sort?

Best case O(n log n). Average case O(n log n). Worst case O(n²). Space complexity is O(log n) stack. Balanced partitions give log n depth; a pathological pivot gives n depth.

Quick sort

medium

After one partition the pivot is in its final position forever. Choose 'last element' and feed it a sorted array to watch the O(n²) worst case unfold, then switch to median-of-three and watch it disappear.

Best O(n log n)Average O(n log n)Worst O(n²)Space O(log n) stackNot stableIn place

Loading the quick sort engine…

Where to go next

Merge sort

medium

Split to single elements, then merge back in order.

Heap sort

medium

Build a heap in the array, then extract the maximum n times.

Dutch national flag

medium

Sort 0s, 1s and 2s in a single pass.