Quick Sort Algorithm
The quick sort algorithm picks a pivot, moves smaller numbers to its left and larger ones to its right, then sorts each side the same way. It is one of the fastest general-purpose sorts in practice, with an O(n log n) average case. Step through it below, then read how it works and where it can go wrong.
Try it: Pick the last element as the pivot, move smaller numbers to its left and larger to its right, then sort each side the same way. Click the Next button to perform one step at a time.
Time: O(n log n) average, O(n²) worst · Space: O(log n) · Not stable
What is Quick Sort?
Quick Sort is a divide-and-conquer algorithm. It picks a pivot, partitions the list so that smaller elements are on the left and larger ones on the right, and then sorts each side recursively.
Key insight: After partitioning, the pivot is already in its final position. A good pivot splits the list roughly in half, which gives O(n log n); a consistently bad pivot (for example the smallest element every time) degrades it to O(n²).
Quick Sort Time Complexity
| Measure | Value |
|---|---|
| Best case | O(n log n) |
| Average case | O(n log n) |
| Worst case | O(n²) |
| Space | O(log n) |
| Stable | No |
For a formal definition and complexity analysis, see the NIST Dictionary of Algorithms and Data Structures entry for quicksort.
Algorithm Steps
- Choose a pivot (this demo uses the last element).
- Partition: move elements smaller than the pivot to the left.
- Place the pivot between the two parts; it is now in its final position.
- Recursively sort the left part.
- Recursively sort the right part.
Advantages and Disadvantages
Advantages
- Very fast in practice thanks to cache-friendly in-place partitioning
- Average O(n log n) with small constants
- Needs only O(log n) extra stack space
Disadvantages
- Worst case O(n²) with poor pivots
- Not stable
- Recursive, so very deep recursion is possible on bad inputs
Real-World Applications
- General-purpose sorting in many standard libraries (often as introsort)
- Sorting large arrays in memory, where it is usually the fastest in practice
- Selecting the k-th smallest element (Quickselect)
When to Use Quick Sort
Use it for sorting large in-memory arrays when average speed matters most. Use random or median-of-three pivots to avoid the worst case, or choose Merge/Heap Sort when guarantees are required.
Quick Sort Implementation
Python
def quick_sort(arr, lo=0, hi=None):
if hi is None:
hi = len(arr) - 1
if lo < hi:
pivot = arr[hi] # last element as pivot
i = lo
for j in range(lo, hi):
if arr[j] < pivot:
arr[i], arr[j] = arr[j], arr[i]
i += 1
arr[i], arr[hi] = arr[hi], arr[i] # pivot to its final place
quick_sort(arr, lo, i - 1)
quick_sort(arr, i + 1, hi)
return arrJavaScript
function quickSort(arr, lo = 0, hi = arr.length - 1) {
if (lo < hi) {
const pivot = arr[hi]; // last element as pivot
let i = lo;
for (let j = lo; j < hi; j++) {
if (arr[j] < pivot) {
[arr[i], arr[j]] = [arr[j], arr[i]];
i++;
}
}
[arr[i], arr[hi]] = [arr[hi], arr[i]]; // pivot to its final place
quickSort(arr, lo, i - 1);
quickSort(arr, i + 1, hi);
}
return arr;
}FAQ
When does quick sort hit its O(n²) worst case?
When the pivot is repeatedly the smallest or largest value, so each partition only removes one element. With the last element as pivot (as in this demo), an already sorted or reverse-sorted list triggers it. Choosing a random or median-of-three pivot makes this very unlikely.
Is quick sort stable?
No. Partitioning swaps elements across long distances, so equal values can change their relative order.
Why is quick sort fast in practice?
It sorts in place, works on neighbouring memory (cache-friendly) and has a small inner loop. Library sorts such as introsort start with quick sort and fall back to Heap Sort if recursion gets too deep, to cap the worst case at O(n log n).
