AlgoScope

Quick Sort

Pick a pivot, push everything smaller left, and the pivot is home for good.

Sorting, algorithm, intermediate
Index 5 is in its final position and will not be touched again.range 0-650114223347586ipivot
Index 5 is in its final position and will not be touched again.range 0-650114223347586ipivot

Quick Sort: Seven values

Step, step 10 of 29

Index 5 is finished. The pivot never has to move again.

Cost

Best
O(n log n)
Average
O(n log n)
Worst
O(n^2)
Space
O(log n)

Space is recursion depth. O(n) worst case without tail-call on the larger side.

Properties

  • Yes: Comparison based
  • No: Stable
  • Yes: In place
  • No: Adaptive
  • No: Online

Before this

Variants

  • Two-Way (Lomuto)Single boundary partition.
  • Hoare PartitionPointers converge from both ends.
  • Randomized PivotRandom pivot makes the worst case unlikely.

Leads to

Topics that need this one first.

Taught by the same lesson

Quick Sort covers these too, in the same run.