15% off all plans & roadmaps Use code
See plansOpening your learning path
Progress is saved as you study.
Quick sort partitions a range around a pivot so smaller values sit on its left and larger values on its right, then sorts each side recursively. The pivot is already in its final place. It runs in O(n log n) time when splits are roughly balanced, O(n^2) when they are repeatedly lopsided, and it sorts in place.
| Balanced splits | O(n log n): O(n) partition work per level, about log n levels |
|---|---|
| Worst case | O(n^2), for example sorted or reverse-sorted input with a last-element pivot |
| Extra space | O(1) partition storage, plus recursion stack: O(log n) balanced, O(n) unbalanced |
| Stable | No, a basic in-place version can reorder equal keys |
| Recursive ranges | lo..p-1 and p+1..hi, never including the pivot |
Quick Sort needs two earlier ideas:
This lesson uses inclusive array bounds:
lo is the first index in the active range.hi is the last index in the active range.lo >= hi.We will use a stated pivot rule throughout:
Choose the last element of the active range as the pivot.
The partition helper used here places values less than or equal to the pivot on its left and values greater than the pivot on its right.
Sources for the partitioning model and analysis:
Start with this array:
1input: [3, 1, 4, 2]| Index | 0 | 1 | 2 | 3 |
|---|---|---|---|---|
| Value | 3 | 1 | 4 | 2 |
The first active range is indices 0 through 3.
1QuickSort(array, lo = 0, hi = 3)The last element is the pivot:
1pivot = array[3] = 2Quick Sort first partitions around 2.
After that partition, the required state is:
1[1, 2, 4, 3]
2 ^
3 pivot at index 1Now 2 is in its final position for this range:
<= 2> 2The remaining work splits into two independent ranges:
1left range: indices 0..0 -> [1]
2right range: indices 2..3 -> [4, 3]The pivot itself is excluded from both recursive calls.
Use a partition method with two indices:
j scans each element before the pivot.i marks the end of the region containing values <= pivot.At the beginning, no values have been placed into the left region, so:
1i = lo - 1 = -1
2j starts at lo = 0
3pivot = 2Initial array:
| Index | 0 | 1 | 2 | 3 |
|---|---|---|---|---|
| Value | 3 | 1 | 4 | 2 |
| Role | scan area | scan area | scan area | pivot |
1j = 0
2array[j] = 3
33 <= 2 is falseDo not move 3. It belongs on the pivot's right side.
1array: [3, 1, 4, 2]
2i = -11j = 1
2array[j] = 1
31 <= 2 is trueMove the boundary one position right:
1i = 0Swap array[i] and array[j]:
1swap array[0] and array[1]| Index | 0 | 1 | 2 | 3 |
|---|---|---|---|---|
| Before | 3 | 1 | 4 | 2 |
| After | 1 | 3 | 4 | 2 |
Now array[0] = 1 is in the confirmed left region.
1array: [1, 3, 4, 2]
2i = 01j = 2
2array[j] = 4
34 <= 2 is falseDo not move 4.
1array: [1, 3, 4, 2]
2i = 0The scan is complete. Values through index i are <= 2. Values from i + 1 through hi - 1 are > 2.
The next available position after the left region is:
1i + 1 = 1Swap the pivot into that position:
1swap array[1] and array[3]| Index | 0 | 1 | 2 | 3 |
|---|---|---|---|---|
| Before | 1 | 3 | 4 | 2 |
| After | 1 | 2 | 4 | 3 |
The partition returns pivot index 1.
1[1, 2, 4, 3]
2 ^The next recursive calls are:
1QuickSort(array, 0, 0) // left of pivot
2QuickSort(array, 2, 3) // right of pivotAfter a partition call completes, the pivot has a guaranteed boundary around it.
For the returned pivot index p:
1array[lo..p-1] <= array[p]
2array[p+1..hi] > array[p]In the example, partition returned p = 1:
1[1, 2, 4, 3]So:
1[1] <= 2
2[4, 3] > 2The left and right ranges may remain unsorted.
1right range: [4, 3]Every value in the left range belongs before the pivot. Every value in the right range belongs after it. Quick Sort can sort those ranges separately.
The invariant for completed partition calls is:
The pivot is in a final position relative to that call's range. Every left value satisfies the left relation, every right value satisfies the right relation, and recursive calls operate only inside those two ranges.
The partition result determines the next steps.
p be the pivot's final index.p.p.The bounds must exclude the pivot:
1left: lo to p - 1
2right: p + 1 to hiDo not recurse on lo..p or p..hi. The pivot is already final. Including it can repeat the same range forever.
For the example:
1QuickSort([3,1,4,2], 0, 3)
2
3partition returns p = 1
4array becomes [1,2,4,3]
5
6sort 0..0 -> [1]
7sort 2..3 -> [4,3]The right range partitions around its last element, 3:
1[4,3] -> [3,4]The full array becomes:
1[1,2,3,4]The algorithm mutates the input array in place. It does not create another array for the sorted result.
PartitionInput
array: a mutable arraylo, hi: inclusive bounds satisfying 0 <= lo <= hi < length(array)Behavior
array[hi] as the pivot.array[lo..hi].p.array[lo..p-1] <= array[p]array[p+1..hi] > array[p]11 function Partition(array, lo, hi) -> integer
22 pivot = array[hi]
33 i = lo - 1
44
55 for j = lo to hi - 1
66 if array[j] <= pivot
77 i = i + 1
88 swap array[i] and array[j]
99
1010 swap array[i + 1] and array[hi]
1111 return i + 1QuickSortInput
array: a mutable arraylo, hi: inclusive boundslo = 0 and hi = length(array) - 1.lo may be greater than hi.Return value
Mutation behavior
array[lo..hi] in nondecreasing order.11 function QuickSort(array, lo, hi) -> nothing
22 if lo >= hi
33 return
44
55 p = Partition(array, lo, hi)
66 QuickSort(array, lo, p - 1)
77 QuickSort(array, p + 1, hi)Use the original array:
1array = [3, 1, 4, 2]
2QuickSort(array, 0, 3)QuickSort(array, 0, 3)1QuickSort line 2: lo >= hi?
20 >= 3 is falseContinue.
1QuickSort line 5: p = Partition(array, 0, 3)Enter Partition.
1Partition line 2: pivot = array[3] = 2
2Partition line 3: i = 0 - 1 = -1Loop begins.
1Partition line 5: j = 0
2Partition line 6: array[0] <= pivot?
33 <= 2 is falseDo not execute lines 7 and 8.
1array = [3, 1, 4, 2]
2i = -1Next loop iteration:
1Partition line 5: j = 1
2Partition line 6: array[1] <= pivot?
31 <= 2 is true
4Partition line 7: i = 0
5Partition line 8: swap array[0] and array[1]1array = [1, 3, 4, 2]Next loop iteration:
1Partition line 5: j = 2
2Partition line 6: array[2] <= pivot?
34 <= 2 is falseThe loop ends.
1Partition line 10: swap array[i + 1] and array[hi]
2swap array[1] and array[3]1array = [1, 2, 4, 3]1Partition line 11: return i + 1 = 1Back in QuickSort:
1QuickSort line 5: p = 1
2QuickSort line 6: QuickSort(array, 0, 0)QuickSort(array, 0, 0)1QuickSort line 2: 0 >= 0 is true
2QuickSort line 3: returnThe range [1] is already sorted.
Back in the first call:
1QuickSort line 7: QuickSort(array, 2, 3)QuickSort(array, 2, 3)1QuickSort line 2: 2 >= 3 is false
2QuickSort line 5: p = Partition(array, 2, 3)Enter Partition.
1Partition line 2: pivot = array[3] = 3
2Partition line 3: i = 2 - 1 = 1Loop:
1Partition line 5: j = 2
2Partition line 6: array[2] <= pivot?
34 <= 3 is falseThe loop ends.
1Partition line 10: swap array[i + 1] and array[hi]
2swap array[2] and array[3]1array = [1, 2, 3, 4]1Partition line 11: return 2Back in QuickSort(array, 2, 3):
1QuickSort line 6: QuickSort(array, 2, 1)This is an empty range.
1QuickSort line 2: 2 >= 1 is true
2QuickSort line 3: returnThen:
1QuickSort line 7: QuickSort(array, 3, 3)This range has one element.
1QuickSort line 2: 3 >= 3 is true
2QuickSort line 3: returnAll calls return. The final array is:
1[1, 2, 3, 4]We use a recursive argument based on the partition postcondition.
If lo >= hi, the active range has:
Both are already sorted, so returning is correct.
For a range array[lo..hi], Partition returns an index p such that:
1array[lo..p-1] <= array[p]
2array[p+1..hi] > array[p]The pivot at array[p] needs no further movement within this range. No value from the left range belongs after it, and no value from the right range belongs before it.
The recursive calls are:
1QuickSort(array, lo, p - 1)
2QuickSort(array, p + 1, hi)These ranges contain every index in the original range except p:
1lo .. p - 1, p, p + 1 .. hiSo no element is omitted.
The calls exclude the pivot because the pivot is already final.
Assume the recursive calls correctly sort their smaller ranges.
Then:
array[lo..p-1] is sorted.array[p+1..hi] is sorted.<= array[p].> array[p].So the full range has the form:
1sorted left range, pivot, sorted right rangeThat entire sequence is sorted in nondecreasing order.
Because the base cases are sorted and each non-base call partitions first and recursively sorts both remaining ranges, QuickSort correctly sorts the requested range.
For a subarray of length m, the partition loop examines each element before the pivot once:
1j = lo through hi - 1That is m - 1 loop iterations.
Each iteration performs one comparison with the pivot and may perform a swap. The final pivot swap is one more constant-time operation.
So one partition costs:
1O(m) timeIf partitions are roughly balanced, each partition divides the work into two ranges of similar size.
At one recursion level, the active subarrays together contain at most n elements. Partitioning across that level therefore costs O(n) total work.
If each split is roughly balanced, the number of levels is O(log n).
1O(n) work per level × O(log n) levels = O(n log n)With the last-element pivot rule, already sorted input can produce a pivot at the end every time.
For:
1[1, 2, 3, 4]the pivot is 4. Every other value is <= 4, so the pivot finishes at the last index. The recursive subproblems have sizes:
13 and 0Then the size-3 left range produces subproblems of sizes:
12 and 0The partition work is:
1n + (n - 1) + (n - 2) + ... + 1This sum is:
1O(n^2)Reverse-sorted input also produces repeatedly unbalanced calls with this pivot rule:
1[4, 3, 2, 1]Here the pivot 1 moves to the beginning, leaving subproblems of sizes:
10 and n - 1The partition helper uses a constant number of local variables:
1pivot, i, jSo in-place partitioning uses:
1O(1) local storageQuick Sort also stores recursive calls on the call stack:
O(log n).O(n).Therefore, auxiliary space from recursion is:
1balanced recursion: O(log n)
2unbalanced recursion: O(n)The array is sorted in place. A basic in-place Quick Sort implementation can change the relative order of equal values during swaps.
Incorrect recursive bound:
1QuickSort(array, lo, p)instead of:
1QuickSort(array, lo, p - 1)Smallest exposing input:
1[1, 2]With the last element as pivot, partition returns:
1p = 1The incorrect call repeats the original range:
1QuickSort(array, 0, 1)It partitions again, returns 1 again, and repeats without reaching a smaller range.
Correction:
1QuickSort(array, lo, p - 1)
2QuickSort(array, p + 1, hi)Incorrect idea:
1QuickSort left side
2QuickSort right side
3then choose or place a pivotSmallest exposing input:
1[3, 1, 2]Before partitioning, there is no established pivot boundary. These questions have no valid answer:
1Which indices are definitely left of the pivot?
2Which indices are definitely right of the pivot?The recursive ranges are arbitrary, so they do not follow from a sorting guarantee.
Correction:
1p = Partition(array, lo, hi)
2QuickSort(array, lo, p - 1)
3QuickSort(array, p + 1, hi)Partition must happen first because it defines the two valid subproblems.
O(n log n) for every pivot outcomeIncorrect claim:
1Quick Sort always takes O(n log n) time.Exposing input under the last-element pivot rule:
1[1, 2, 3, 4]The pivot is always the largest value in its active range. The subproblem sizes become:
13 and 0
22 and 0
31 and 0The work follows:
1n + (n - 1) + ... + 1which is O(n^2).
Correction:
O(n log n).O(n^2).Incorrect claim:
1Equal values always keep their original relative order.Exposing tagged input:
1[(2,A), (1,X), (2,B)]The numeric key is the first component. A swap-based in-place partition can move equal-key records past each other. A resulting sorted sequence can place (2,B) before (2,A) even though (2,A) appeared first in the input.
The numeric keys are sorted, but the equal records changed order.
Correction:
1Do not promise stability for a basic in-place Quick Sort implementation.| Input | Behavior |
|---|---|
[] | Initial range has lo > hi; return unchanged. |
[7] | Initial range has lo == hi; return unchanged. |
[2,1] | Pivot 1 moves to index 0; result is [1,2]. |
[1,2,3,4] | Last pivot repeatedly creates a large left subproblem and an empty right subproblem. |
[4,3,2,1] | Last pivot repeatedly creates an empty left subproblem and a large right subproblem. |
[2,2,2] | Sorts correctly, but simple two-way partitioning can create unbalanced recursive ranges. |
Implement in-place Quick Sort with these requirements:
lo and hi bounds.lo >= hi.lo..p-1 and p+1..hi.The executable tests will verify sorted permutations for:
1empty arrays
2arrays with duplicates
3arrays with negative values
4already sorted arrays
5reverse-sorted arrays1
2comparisons = 0
3
4def partition(a, lo, hi):
5 global comparisons
6 pivot = a[hi] # last element is the pivot
7 i = lo - 1 # end of the region of values <= pivot
8 for j in range(lo, hi):
9 comparisons += 1
10 if a[j] <= pivot:
11 i += 1
12 a[i], a[j] = a[j], a[i]
13 a[i + 1], a[hi] = a[hi], a[i + 1] # pivot lands between the two regions
14 return i + 1
15
16def quick_sort(a, lo, hi):
17 if lo >= hi:
18 return
19 p = partition(a, lo, hi)
20 quick_sort(a, lo, p - 1) # the pivot is final, so exclude it
21 quick_sort(a, p + 1, hi)
22
23def count_comparisons(a):
24 global comparisons
25 comparisons = 0
26 quick_sort(a, 0, len(a) - 1)
27 return comparisons
28
29nums = [3, 1, 4, 2]
30quick_sort(nums, 0, len(nums) - 1)
31print(nums)
32print("balanced input, 7 values:", count_comparisons([3, 1, 2, 6, 5, 7, 4]), "comparisons")
33print("sorted input, 7 values:", count_comparisons([1, 2, 3, 4, 5, 6, 7]), "comparisons")1
2import java.util.Arrays;
3
4public class Main {
5 static int comparisons = 0;
6
7 static int partition(int[] a, int lo, int hi) {
8 int pivot = a[hi]; // last element is the pivot
9 int i = lo - 1; // end of the region of values <= pivot
10 for (int j = lo; j < hi; j++) {
11 comparisons++;
12 if (a[j] <= pivot) {
13 i++;
14 int tmp = a[i]; a[i] = a[j]; a[j] = tmp;
15 }
16 }
17 int tmp = a[i + 1]; a[i + 1] = a[hi]; a[hi] = tmp; // pivot lands between the two regions
18 return i + 1;
19 }
20
21 static void quickSort(int[] a, int lo, int hi) {
22 if (lo >= hi) return;
23 int p = partition(a, lo, hi);
24 quickSort(a, lo, p - 1); // the pivot is final, so exclude it
25 quickSort(a, p + 1, hi);
26 }
27
28 static int countComparisons(int[] a) {
29 comparisons = 0;
30 quickSort(a, 0, a.length - 1);
31 return comparisons;
32 }
33
34 public static void main(String[] args) {
35 int[] nums = {3, 1, 4, 2};
36 quickSort(nums, 0, nums.length - 1);
37 System.out.println(Arrays.toString(nums));
38 System.out.println("balanced input, 7 values: " + countComparisons(new int[]{3, 1, 2, 6, 5, 7, 4}) + " comparisons");
39 System.out.println("sorted input, 7 values: " + countComparisons(new int[]{1, 2, 3, 4, 5, 6, 7}) + " comparisons");
40 }
41}1
2#include <iostream>
3#include <utility>
4#include <vector>
5using namespace std;
6
7int comparisons = 0;
8
9int partition(vector<int>& a, int lo, int hi) {
10 int pivot = a[hi]; // last element is the pivot
11 int i = lo - 1; // end of the region of values <= pivot
12 for (int j = lo; j < hi; j++) {
13 comparisons++;
14 if (a[j] <= pivot) {
15 i++;
16 swap(a[i], a[j]);
17 }
18 }
19 swap(a[i + 1], a[hi]); // pivot lands between the two regions
20 return i + 1;
21}
22
23void quickSort(vector<int>& a, int lo, int hi) {
24 if (lo >= hi) return;
25 int p = partition(a, lo, hi);
26 quickSort(a, lo, p - 1); // the pivot is final, so exclude it
27 quickSort(a, p + 1, hi);
28}
29
30int countComparisons(vector<int> a) {
31 comparisons = 0;
32 quickSort(a, 0, (int)a.size() - 1);
33 return comparisons;
34}
35
36int main() {
37 vector<int> nums = {3, 1, 4, 2};
38 quickSort(nums, 0, (int)nums.size() - 1);
39 cout << "[";
40 for (size_t i = 0; i < nums.size(); i++) cout << (i ? ", " : "") << nums[i];
41 cout << "]" << endl;
42 cout << "balanced input, 7 values: " << countComparisons({3, 1, 2, 6, 5, 7, 4}) << " comparisons" << endl;
43 cout << "sorted input, 7 values: " << countComparisons({1, 2, 3, 4, 5, 6, 7}) << " comparisons" << endl;
44}1
2let comparisons = 0;
3
4function partition(a, lo, hi) {
5 const pivot = a[hi]; // last element is the pivot
6 let i = lo - 1; // end of the region of values <= pivot
7 for (let j = lo; j < hi; j++) {
8 comparisons++;
9 if (a[j] <= pivot) {
10 i++;
11 [a[i], a[j]] = [a[j], a[i]];
12 }
13 }
14 [a[i + 1], a[hi]] = [a[hi], a[i + 1]]; // pivot lands between the two regions
15 return i + 1;
16}
17
18function quickSort(a, lo, hi) {
19 if (lo >= hi) return;
20 const p = partition(a, lo, hi);
21 quickSort(a, lo, p - 1); // the pivot is final, so exclude it
22 quickSort(a, p + 1, hi);
23}
24
25function countComparisons(a) {
26 comparisons = 0;
27 quickSort(a, 0, a.length - 1);
28 return comparisons;
29}
30
31const nums = [3, 1, 4, 2];
32quickSort(nums, 0, nums.length - 1);
33console.log(`[${nums.join(', ')}]`);
34console.log(`balanced input, 7 values: ${countComparisons([3, 1, 2, 6, 5, 7, 4])} comparisons`);
35console.log(`sorted input, 7 values: ${countComparisons([1, 2, 3, 4, 5, 6, 7])} comparisons`);O(n log n) when partitions are roughly balanced and O(n^2) when they are repeatedly lopsided. One partition of m elements costs O(m). Balanced splits give about log n levels of O(n) work, lopsided ones give n levels.
On [1, 2, 3, 4] the pivot 4 is the largest value, so the split is 3 and 0. The next range splits 2 and 0, and so on. The comparisons add up to n + (n - 1) + ... + 1, which is O(n^2).
No, not in the basic in-place form. Partition swaps carry equal keys past each other. With a last-element pivot, [(2,A), (2,B), (1,X)] sorts to (1,X), (2,B), (2,A).
Choose the pivot so splits stay balanced, for example a random element or the median of the first, middle and last values. The lesson uses the last element on purpose, to make the worst case easy to see.
Quick sort does its work while partitioning and sorts in place, but can hit O(n^2) and is not stable. Merge sort does its work while merging, is O(n log n) always and stable, and needs an O(n) auxiliary array.
Calling QuickSort(lo, p) on [1, 2] repeats the same range forever, because the partition returns p = 1 again. Using lo..p-1 and p+1..hi shrinks the range every time.