Quick Sort
Last updated
Quicksort is a divide-and-conquer algorithm that sorts around a "pivot". It picks a pivot element, then partitions the array so everything smaller comes before it and everything larger comes after - which locks the pivot into its final sorted position. It then recurses on the left and right partitions. This visualization uses the Lomuto scheme with the last element as pivot. Press play to watch the partitioning and pivot placement.
Quicksort is usually the fastest general-purpose sort in practice thanks to good cache behavior and in-place partitioning, averaging O(n log n). Its worst case is O(n²) (e.g. an already-sorted array with a poor pivot choice), which good pivot strategies like median-of-three or randomization avoid.
Time & space complexity
| Case | Complexity | Notes |
|---|---|---|
| Best case | O(n log n) | Balanced partitions |
| Average case | O(n log n) | Random order |
| Worst case | O(n²) | Consistently unbalanced pivots |
| Space | O(log n) | Recursion stack (in-place partition) |
| Stable | No | Partition swaps reorder equal elements |
Step by step
| Step | What happens |
|---|---|
| 1 | Choose a pivot (here, the last element of the range). |
| 2 | Partition: move all elements smaller than the pivot to its left. |
| 3 | Swap the pivot into the boundary - it is now in final position. |
| 4 | Recursively quicksort the left partition. |
| 5 | Recursively quicksort the right partition. |
Worked example
Sorting [5, 2, 4, 1] with the Lomuto scheme (last element as pivot):
| Pass | Array | Action |
|---|---|---|
| Start | [5, 2, 4, 1] | Partition the whole range; pivot is 1 (last element). |
| 1 | [1, 2, 4, 5] | Nothing is smaller than 1, so swap 1 into index 0; pivot 1 is now final. Recurse right on [2, 4, 5]. |
| 2 | [1, 2, 4, 5] | Partition [2, 4, 5] with pivot 5; both 2 and 4 are smaller, so 5 stays at the end and is final. Recurse left on [2, 4]. |
| 3 | [1, 2, 4, 5] | Partition [2, 4] with pivot 4; 2 is smaller, so 4 stays put and is final. 2 is a single element, so it is already sorted. |
| Done | [1, 2, 4, 5] | Every pivot is locked in place; the array is sorted. |
When to use quicksort
| Use it when | Avoid it when |
|---|---|
| You need a fast, general-purpose in-memory sort with small constant factors. | You need guaranteed O(n log n) worst-case time (use heap sort or merge sort). |
Memory is tight - partitioning is in place and needs only O(log n) stack space. | You need a stable sort that preserves the order of equal keys. |
| Data is in a random or unknown order and you use a randomized or median-of-three pivot. | The input is already sorted or nearly sorted and the pivot is fixed, triggering O(n²). |
| Good cache locality matters, since quicksort accesses memory sequentially. | You are sorting a linked list, where merge sort avoids the random access quicksort relies on. |
Quick Sort code
A clean, runnable Quick Sort implementation in Python, JavaScript, Java, C++, C. Pick a language, copy the code, or open it pre-loaded in the Coddy Playground.
Quick Sort code in Python
Python
1def quick_sort(a, low=0, high=None):2 if high is None:3 high = len(a) - 14 if low < high:5 p = partition(a, low, high)6 quick_sort(a, low, p - 1)7 quick_sort(a, p + 1, high)8 return a9
10
11def partition(a, low, high):12 # Lomuto partition: everything < pivot moves left of it13 pivot = a[high]14 i = low15 for j in range(low, high):16 if a[j] < pivot:17 a[i], a[j] = a[j], a[i]18 i += 119 a[i], a[high] = a[high], a[i]20 return i21
22
23nums = [10, 7, 8, 9, 1, 5]24print("Before:", nums)25quick_sort(nums)26print("After: ", nums)Quick Sort code in JavaScript
JavaScript
1function quickSort(a, lo = 0, hi = a.length - 1) {2 if (lo >= hi) return a;3 const p = partition(a, lo, hi);4 quickSort(a, lo, p - 1);5 quickSort(a, p + 1, hi);6 return a;7}8
9// Lomuto partition: last element is the pivot10function partition(a, lo, hi) {11 const pivot = a[hi];12 let i = lo;13 for (let j = lo; j < hi; j++) {14 if (a[j] < pivot) {15 [a[i], a[j]] = [a[j], a[i]];16 i++;17 }18 }19 [a[i], a[hi]] = [a[hi], a[i]];20 return i;21}22
23const data = [5, 2, 9, 1, 7, 3];24console.log("Before:", data);25console.log("Sorted:", quickSort([...data]));Quick Sort code in Java
Java
1import java.util.Arrays;2
3public class Main {4 static void quickSort(int[] arr, int low, int high) {5 if (low >= high) return;6 int p = partition(arr, low, high);7 quickSort(arr, low, p - 1);8 quickSort(arr, p + 1, high);9 }10
11 // Lomuto partition: last element is the pivot12 static int partition(int[] arr, int low, int high) {13 int pivot = arr[high];14 int i = low - 1;15 for (int j = low; j < high; j++) {16 if (arr[j] < pivot) swap(arr, ++i, j);17 }18 swap(arr, i + 1, high);19 return i + 1;20 }21
22 static void swap(int[] arr, int a, int b) {23 int tmp = arr[a];24 arr[a] = arr[b];25 arr[b] = tmp;26 }27
28 public static void main(String[] args) {29 int[] arr = {10, 7, 8, 9, 1, 5};30 System.out.println("Before: " + Arrays.toString(arr));31 quickSort(arr, 0, arr.length - 1);32 System.out.println("After: " + Arrays.toString(arr));33 }34}Quick Sort code in C++
C++
1#include <iostream>2#include <utility>3#include <vector>4
5void printVec(const std::vector<int>& a) {6 for (int x : a) std::cout << x << " ";7 std::cout << "\n";8}9
10// Lomuto partition: place the pivot in its final position11int partition(std::vector<int>& a, int lo, int hi) {12 int pivot = a[hi];13 int i = lo;14 for (int j = lo; j < hi; ++j) {15 if (a[j] < pivot) std::swap(a[i++], a[j]);16 }17 std::swap(a[i], a[hi]);18 return i;19}20
21void quickSort(std::vector<int>& a, int lo, int hi) {22 if (lo >= hi) return;23 int p = partition(a, lo, hi);24 quickSort(a, lo, p - 1);25 quickSort(a, p + 1, hi);26}27
28int main() {29 std::vector<int> data = {10, 7, 8, 9, 1, 5};30 std::cout << "Before: ";31 printVec(data);32 quickSort(data, 0, static_cast<int>(data.size()) - 1);33 std::cout << "After: ";34 printVec(data);35 return 0;36}Quick Sort code in C
C
1#include <stdio.h>2
3void printArr(const int a[], int n) {4 for (int i = 0; i < n; i++) printf("%d ", a[i]);5 printf("\n");6}7
8void swap(int* x, int* y) {9 int tmp = *x;10 *x = *y;11 *y = tmp;12}13
14// Lomuto partition: place the pivot in its final position15int partition(int a[], int lo, int hi) {16 int pivot = a[hi];17 int i = lo;18 for (int j = lo; j < hi; j++) {19 if (a[j] < pivot) swap(&a[i++], &a[j]);20 }21 swap(&a[i], &a[hi]);22 return i;23}24
25void quickSort(int a[], int lo, int hi) {26 if (lo >= hi) return;27 int p = partition(a, lo, hi);28 quickSort(a, lo, p - 1);29 quickSort(a, p + 1, hi);30}31
32int main(void) {33 int data[] = {10, 7, 8, 9, 1, 5};34 int n = sizeof(data) / sizeof(data[0]);35 printf("Before: ");36 printArr(data, n);37 quickSort(data, 0, n - 1);38 printf("After: ");39 printArr(data, n);40 return 0;41}Quick Sort FAQ
What is the time complexity of quicksort?
Quicksort averages
O(n log n) and is O(n log n) in the best case, but degrades to O(n²) in the worst case when partitions are consistently unbalanced. Randomized or median-of-three pivots make the worst case very unlikely.Is quicksort stable?
No. The standard in-place partition swaps distant elements, which can change the relative order of equal keys. Stable variants exist but give up quicksort’s in-place advantage.
Why is quicksort often faster than merge sort?
Quicksort partitions in place with excellent cache locality and no extra buffer, so its constant factors are small. Merge sort matches its
O(n log n) bound but pays for an O(n) buffer and more data movement.Quicksort vs merge sort - which should I use?
Choose quicksort for fast in-place sorting of arrays in memory, where its small constants usually win. Choose merge sort when you need a stable sort, a guaranteed
O(n log n) worst case, or you are sorting linked lists or external data that does not fit in RAM.Why does quicksort become O(n²) on a sorted array?
With a fixed pivot such as the first or last element, an already-sorted input makes every partition split off just one element, producing
n levels of recursion instead of log n. Choosing the pivot randomly or with median-of-three breaks this pattern and restores O(n log n) behavior.What is the difference between the Lomuto and Hoare partition schemes?
The Lomuto scheme uses a single index scanning left to right and is simpler to code, which is why this visualization uses it. The Hoare scheme uses two pointers moving inward and typically does fewer swaps, making it faster in practice, but it does not place the pivot in its final position during the partition step.
Related resources
More visualizations
