Skip to main content

DSAPath8 mincore

Quick Sort

Quicksort partitions an array around a pivot and recursively sorts the two sides. It is fast in practice on many inputs but has a quadratic worst case without care.

Why This Matters

Quicksort is the sorting algorithm that makes input distribution visible. A good pivot gives balanced subproblems; a bad pivot repeatedly peels off tiny pieces.

Core Idea

Choose a pivot. Partition the array so smaller items come before the pivot and larger items come after it. Recursively sort the partitions.

Worked example: with pivot 3, [4, 1, 3, 2] partitions into [1, 2], 3, [4]; the two sides are then sorted recursively.

CaseTime
balanced partitionsO(nlog⁡n)O(n \log n)
repeatedly worst pivotO(n2)O(n^2)
extra space from recursionusually O(log⁡n)O(\log n) expected

Common Mistakes

  • Saying quicksort is always O(nlog⁡n)O(n \log n). The worst case is quadratic.
  • Choosing the first element as pivot on already sorted data.
  • Getting partition boundary cases wrong when duplicates appear.

Exercises

  • Partition [8, 3, 7, 1, 5] around pivot 5.
  • Explain why random pivot choice helps.
  • Compare quicksort and merge sort on stability and extra space.

Next Topics

References

  • Cormen, Leiserson, Rivest, Stein. Introduction to Algorithms (4th ed., 2022). Ch. 7.
  • Sedgewick and Wayne. Algorithms (4th ed., 2011). Ch. 2.