Skip to content
Back to AlgorithmsAll lessons

Algorithms

Quick Sort

O(n log n) time on average · O(n²) time in the worst case, with bad pivot choices · O(log n) space for the recursive calls.

The idea, in plain English

Quick sort picks one item as a 'pivot' — a reference point for splitting the list. It puts the rest into two buckets: smaller-than-pivot and bigger-than-pivot. Then it sorts each bucket the same way. It is like organizing papers by placing each one to the left or right of a chosen middle paper.

How it works

  1. 1Pick a pivot item from the list.
  2. 2Put everything smaller on its left, and everything bigger on its right.
  3. 3Repeat the same process on the left and right groups, then join them together.

When you'd use it

This is a common general-purpose sort. It is fast in practice and sorts in place, using little extra memory.

Common beginner mistakes

  • Always picking the first item as the pivot. On already-sorted data, that gives you the slow worst case.
  • Making off-by-one errors when you split the list into the two groups.

Try it — edit and run

Click the code to edit · press ⌘/Ctrl+↵ to run

Editable code. Tab and Shift+Tab indent. Press Escape, then Tab, to move focus out of the editor.

Expected output — hit Run to try it
Before: 5 2 9 1 5 6
Sorted: 1 2 5 5 6 9

See it in motion

Watch it sortQuick sortO(n log n) time on average · O(n²) time in the worst case, with bad pivot choices · O(log n) space for the recursive calls.

Ready. Press play to watch it sort.

0
Comparisons
0
Writes
0/28
Step
0.0s
Time
ComparingSwappingPivotSorted

Not sure this is the right topic? See the learning paths → or where this leads →