Core · Module 8 · Lesson 3 of 5

Quick sort and partitioning

Partition the array around a pivot so that smaller elements come first, then sort each side. Quick sort is O(n log n) on average, works in place, and with good pivots and a fallback it never hits its O(n²) worst case.

ProAbout 15 minutes

By the end you can

Partition an array around a pivot, and trace the Lomuto scheme
Explain quick sort's average O(n log n), its O(n²) worst case, and how pivot choice and introsort avoid it
Use partitioning on its own: three-way partitions and quickselect

Builds on Merge sort.

01 · A question first

Quick sort's worst case is O(n²), worse than merge sort's guaranteed O(n log n). Yet for decades it has been the standard way to sort arrays of numbers in C, C++ and Java. What makes it worth that risk, and how do libraries take the risk away?

Make a guess before you read on.

02 · The idea

Members only

Unlock the full lesson

This lesson is part of the membership. Join to read it in full, along with every other premium deep dive.

What's inside

Partition, then recurse
The Lomuto partition
Average and worst case
Taking the risk away
Why it wins in practice
Partitioning on its own
Pseudocode & Multi-Language Implementations (C++, Java, Python)
Complexity Derivation, Edge Cases & Common Mistakes

See plans Already a member? Sign in

03 · Practice

Practice · medium · LeetCodeSort colorsSort an array of 0s, 1s and 2s in one pass and in place, with a three-way (Dutch national flag) partition.Practice · medium · LeetCodeSort an arraySort an array of integers in O(n log n) without the built-in sort: implement merge sort, then quick sort with a random pivot, and compare.Practice · medium · LeetCodeKth largest element in an arrayFind the kth largest value in an unsorted array with a size-k heap or with quickselect, without fully sorting it.

Asked in interviews

Why is quick sort fast in practice despite its O(n²) worst case?

Something wrong with this lesson? Report a problem