11.5 Quick sort¶
Quick sort is an efficient, widely used sorting algorithm based on divide and conquer.
Its core operation is “partitioning”: choose an array element as the “pivot,” move all smaller elements to its left, and move all larger elements to its right. The partitioning process is shown below.
- Choose the leftmost element as the pivot and initialize pointers
iandjat the two ends of the array. - In a loop, use
ito find the first element greater than the pivot andjto find the first element smaller than it, then swap those elements. - Repeat step
2.untiliandjmeet. Finally, swap the pivot into the boundary between the two subarrays.
Figure 11-8 Steps of partitioning
After partitioning, the original array has three parts: the left subarray, the pivot, and the right subarray. Every element in the left subarray is \(\leq\) the pivot, which is \(\leq\) every element in the right subarray. We now need only sort the two subarrays.
Quick sort's divide-and-conquer strategy
Partitioning reduces the problem of sorting one long array to sorting two shorter arrays.
quick_sort.py
def partition(self, nums: list[int], left: int, right: int) -> int:
"""Two-pointer partitioning"""
# Use nums[left] as the pivot
i, j = left, right
while i < j:
while i < j and nums[j] >= nums[left]:
j -= 1 # Scan from right to left for the first element smaller than the pivot
while i < j and nums[i] <= nums[left]:
i += 1 # Scan from left to right for the first element larger than the pivot
# Swap the elements
nums[i], nums[j] = nums[j], nums[i]
# Swap the pivot into the boundary position between the two subarrays
nums[i], nums[left] = nums[left], nums[i]
return i # Return the pivot index
quick_sort.cpp
/* Two-pointer partitioning */
int partition(vector<int> &nums, int left, int right) {
// Use nums[left] as the pivot
int i = left, j = right;
while (i < j) {
while (i < j && nums[j] >= nums[left])
j--; // Scan from right to left for the first element smaller than the pivot
while (i < j && nums[i] <= nums[left])
i++; // Scan from left to right for the first element larger than the pivot
swap(nums[i], nums[j]); // Swap these two elements
}
swap(nums[i], nums[left]); // Swap the pivot into the boundary position between the two subarrays
return i; // Return the pivot index
}
quick_sort.java
/* Swap the elements */
void swap(int[] nums, int i, int j) {
int tmp = nums[i];
nums[i] = nums[j];
nums[j] = tmp;
}
/* Two-pointer partitioning */
int partition(int[] nums, int left, int right) {
// Use nums[left] as the pivot
int i = left, j = right;
while (i < j) {
while (i < j && nums[j] >= nums[left])
j--; // Scan from right to left for the first element smaller than the pivot
while (i < j && nums[i] <= nums[left])
i++; // Scan from left to right for the first element larger than the pivot
swap(nums, i, j); // Swap these two elements
}
swap(nums, i, left); // Swap the pivot into the boundary position between the two subarrays
return i; // Return the pivot index
}
quick_sort.cs
/* Swap the elements */
void Swap(int[] nums, int i, int j) {
(nums[j], nums[i]) = (nums[i], nums[j]);
}
/* Two-pointer partitioning */
int Partition(int[] nums, int left, int right) {
// Use nums[left] as the pivot
int i = left, j = right;
while (i < j) {
while (i < j && nums[j] >= nums[left])
j--; // Scan from right to left for the first element smaller than the pivot
while (i < j && nums[i] <= nums[left])
i++; // Scan from left to right for the first element larger than the pivot
Swap(nums, i, j); // Swap these two elements
}
Swap(nums, i, left); // Swap the pivot into the boundary position between the two subarrays
return i; // Return the pivot index
}
quick_sort.go
/* Two-pointer partitioning */
func (q *quickSort) partition(nums []int, left, right int) int {
// Use nums[left] as the pivot
i, j := left, right
for i < j {
for i < j && nums[j] >= nums[left] {
j-- // Scan from right to left for the first element smaller than the pivot
}
for i < j && nums[i] <= nums[left] {
i++ // Scan from left to right for the first element larger than the pivot
}
// Swap the elements
nums[i], nums[j] = nums[j], nums[i]
}
// Swap the pivot into the boundary position between the two subarrays
nums[i], nums[left] = nums[left], nums[i]
return i // Return the pivot index
}
quick_sort.swift
/* Two-pointer partitioning */
func partition(nums: inout [Int], left: Int, right: Int) -> Int {
// Use nums[left] as the pivot
var i = left
var j = right
while i < j {
while i < j, nums[j] >= nums[left] {
j -= 1 // Scan from right to left for the first element smaller than the pivot
}
while i < j, nums[i] <= nums[left] {
i += 1 // Scan from left to right for the first element larger than the pivot
}
nums.swapAt(i, j) // Swap these two elements
}
nums.swapAt(i, left) // Swap the pivot into the boundary position between the two subarrays
return i // Return the pivot index
}
quick_sort.js
/* Swap the elements */
swap(nums, i, j) {
let tmp = nums[i];
nums[i] = nums[j];
nums[j] = tmp;
}
/* Two-pointer partitioning */
partition(nums, left, right) {
// Use nums[left] as the pivot
let i = left,
j = right;
while (i < j) {
while (i < j && nums[j] >= nums[left]) {
j -= 1; // Scan from right to left for the first element smaller than the pivot
}
while (i < j && nums[i] <= nums[left]) {
i += 1; // Scan from left to right for the first element larger than the pivot
}
// Swap the elements
this.swap(nums, i, j); // Swap these two elements
}
this.swap(nums, i, left); // Swap the pivot into the boundary position between the two subarrays
return i; // Return the pivot index
}
quick_sort.ts
/* Swap the elements */
swap(nums: number[], i: number, j: number): void {
let tmp = nums[i];
nums[i] = nums[j];
nums[j] = tmp;
}
/* Two-pointer partitioning */
partition(nums: number[], left: number, right: number): number {
// Use nums[left] as the pivot
let i = left,
j = right;
while (i < j) {
while (i < j && nums[j] >= nums[left]) {
j -= 1; // Scan from right to left for the first element smaller than the pivot
}
while (i < j && nums[i] <= nums[left]) {
i += 1; // Scan from left to right for the first element larger than the pivot
}
// Swap the elements
this.swap(nums, i, j); // Swap these two elements
}
this.swap(nums, i, left); // Swap the pivot into the boundary position between the two subarrays
return i; // Return the pivot index
}
quick_sort.dart
/* Swap the elements */
void _swap(List<int> nums, int i, int j) {
int tmp = nums[i];
nums[i] = nums[j];
nums[j] = tmp;
}
/* Two-pointer partitioning */
int _partition(List<int> nums, int left, int right) {
// Use nums[left] as the pivot
int i = left, j = right;
while (i < j) {
while (i < j && nums[j] >= nums[left]) j--; // Scan from right to left for the first element smaller than the pivot
while (i < j && nums[i] <= nums[left]) i++; // Scan from left to right for the first element larger than the pivot
_swap(nums, i, j); // Swap these two elements
}
_swap(nums, i, left); // Swap the pivot into the boundary position between the two subarrays
return i; // Return the pivot index
}
quick_sort.rs
/* Two-pointer partitioning */
fn partition(nums: &mut [i32], left: usize, right: usize) -> usize {
// Use nums[left] as the pivot
let (mut i, mut j) = (left, right);
while i < j {
while i < j && nums[j] >= nums[left] {
j -= 1; // Scan from right to left for the first element smaller than the pivot
}
while i < j && nums[i] <= nums[left] {
i += 1; // Scan from left to right for the first element larger than the pivot
}
nums.swap(i, j); // Swap these two elements
}
nums.swap(i, left); // Swap the pivot into the boundary position between the two subarrays
i // Return the pivot index
}
quick_sort.c
/* Swap the elements */
void swap(int nums[], int i, int j) {
int tmp = nums[i];
nums[i] = nums[j];
nums[j] = tmp;
}
/* Two-pointer partitioning */
int partition(int nums[], int left, int right) {
// Use nums[left] as the pivot
int i = left, j = right;
while (i < j) {
while (i < j && nums[j] >= nums[left]) {
j--; // Scan from right to left for the first element smaller than the pivot
}
while (i < j && nums[i] <= nums[left]) {
i++; // Scan from left to right for the first element larger than the pivot
}
// Swap these two elements
swap(nums, i, j);
}
// Swap the pivot into the boundary position between the two subarrays
swap(nums, i, left);
// Return the pivot index
return i;
}
quick_sort.kt
/* Swap the elements */
fun swap(nums: IntArray, i: Int, j: Int) {
val temp = nums[i]
nums[i] = nums[j]
nums[j] = temp
}
/* Two-pointer partitioning */
fun partition(nums: IntArray, left: Int, right: Int): Int {
// Use nums[left] as the pivot
var i = left
var j = right
while (i < j) {
while (i < j && nums[j] >= nums[left])
j-- // Scan from right to left for the first element smaller than the pivot
while (i < j && nums[i] <= nums[left])
i++ // Scan from left to right for the first element larger than the pivot
swap(nums, i, j) // Swap these two elements
}
swap(nums, i, left) // Swap the pivot into the boundary position between the two subarrays
return i // Return the pivot index
}
quick_sort.rb
### Two-pointer partitioning ###
def partition(nums, left, right)
# Use nums[left] as the pivot
i, j = left, right
while i < j
while i < j && nums[j] >= nums[left]
j -= 1 # Scan from right to left for the first element smaller than the pivot
end
while i < j && nums[i] <= nums[left]
i += 1 # Scan from left to right for the first element larger than the pivot
end
# Swap the elements
nums[i], nums[j] = nums[j], nums[i]
end
# Swap the pivot into the boundary position between the two subarrays
nums[i], nums[left] = nums[left], nums[i]
i # Return the pivot index
end
Visualize execution
11.5.1 Algorithm steps¶
The overall quick sort process is shown below.
- Partition the original array to obtain unsorted left and right subarrays.
- Recursively partition the left and right subarrays.
- Continue until each subarray has length 1, completing the sort.
Figure 11-9 The quick sort process
quick_sort.py
def quick_sort(self, nums: list[int], left: int, right: int):
"""Quick sort"""
# Stop recursing when the subarray has at most one element
if left >= right:
return
# Two-pointer partitioning
pivot = self.partition(nums, left, right)
# Recurse on the left and right subarrays
self.quick_sort(nums, left, pivot - 1)
self.quick_sort(nums, pivot + 1, right)
quick_sort.cpp
/* Quick sort */
void quickSort(vector<int> &nums, int left, int right) {
// Stop recursing when the subarray has at most one element
if (left >= right)
return;
// Two-pointer partitioning
int pivot = partition(nums, left, right);
// Recurse on the left and right subarrays
quickSort(nums, left, pivot - 1);
quickSort(nums, pivot + 1, right);
}
quick_sort.java
/* Quick sort */
void quickSort(int[] nums, int left, int right) {
// Stop recursing when the subarray has at most one element
if (left >= right)
return;
// Two-pointer partitioning
int pivot = partition(nums, left, right);
// Recurse on the left and right subarrays
quickSort(nums, left, pivot - 1);
quickSort(nums, pivot + 1, right);
}
quick_sort.cs
/* Quick sort */
void QuickSort(int[] nums, int left, int right) {
// Stop recursing when the subarray has at most one element
if (left >= right)
return;
// Two-pointer partitioning
int pivot = Partition(nums, left, right);
// Recurse on the left and right subarrays
QuickSort(nums, left, pivot - 1);
QuickSort(nums, pivot + 1, right);
}
quick_sort.go
/* Quick sort */
func (q *quickSort) quickSort(nums []int, left, right int) {
// Stop recursing when the subarray has at most one element
if left >= right {
return
}
// Two-pointer partitioning
pivot := q.partition(nums, left, right)
// Recurse on the left and right subarrays
q.quickSort(nums, left, pivot-1)
q.quickSort(nums, pivot+1, right)
}
quick_sort.swift
/* Quick sort */
func quickSort(nums: inout [Int], left: Int, right: Int) {
// Stop recursing when the subarray has at most one element
if left >= right {
return
}
// Two-pointer partitioning
let pivot = partition(nums: &nums, left: left, right: right)
// Recurse on the left and right subarrays
quickSort(nums: &nums, left: left, right: pivot - 1)
quickSort(nums: &nums, left: pivot + 1, right: right)
}
quick_sort.js
/* Quick sort */
quickSort(nums, left, right) {
// Stop recursing when the subarray has at most one element
if (left >= right) return;
// Two-pointer partitioning
const pivot = this.partition(nums, left, right);
// Recurse on the left and right subarrays
this.quickSort(nums, left, pivot - 1);
this.quickSort(nums, pivot + 1, right);
}
quick_sort.ts
/* Quick sort */
quickSort(nums: number[], left: number, right: number): void {
// Stop recursing when the subarray has zero or one element
if (left >= right) {
return;
}
// Two-pointer partitioning
const pivot = this.partition(nums, left, right);
// Recurse on the left and right subarrays
this.quickSort(nums, left, pivot - 1);
this.quickSort(nums, pivot + 1, right);
}
quick_sort.dart
/* Quick sort */
void quickSort(List<int> nums, int left, int right) {
// Stop recursing when the subarray has at most one element
if (left >= right) return;
// Two-pointer partitioning
int pivot = _partition(nums, left, right);
// Recurse on the left and right subarrays
quickSort(nums, left, pivot - 1);
quickSort(nums, pivot + 1, right);
}
quick_sort.rs
/* Quick sort */
pub fn quick_sort(left: i32, right: i32, nums: &mut [i32]) {
// Stop recursing when the subarray has at most one element
if left >= right {
return;
}
// Two-pointer partitioning
let pivot = Self::partition(nums, left as usize, right as usize) as i32;
// Recurse on the left and right subarrays
Self::quick_sort(left, pivot - 1, nums);
Self::quick_sort(pivot + 1, right, nums);
}
quick_sort.c
/* Quick sort */
void quickSort(int nums[], int left, int right) {
// Stop recursing when the subarray has at most one element
if (left >= right) {
return;
}
// Two-pointer partitioning
int pivot = partition(nums, left, right);
// Recurse on the left and right subarrays
quickSort(nums, left, pivot - 1);
quickSort(nums, pivot + 1, right);
}
quick_sort.kt
/* Quick sort */
fun quickSort(nums: IntArray, left: Int, right: Int) {
// Stop recursing when the subarray has at most one element
if (left >= right) return
// Two-pointer partitioning
val pivot = partition(nums, left, right)
// Recurse on the left and right subarrays
quickSort(nums, left, pivot - 1)
quickSort(nums, pivot + 1, right)
}
quick_sort.rb
### Quick sort ###
def quick_sort(nums, left, right)
# Continue while the subarray contains more than one element
if left < right
# Two-pointer partitioning
pivot = partition(nums, left, right)
# Recurse on the left and right subarrays
quick_sort(nums, left, pivot - 1)
quick_sort(nums, pivot + 1, right)
end
nums
end
Visualize execution
11.5.2 Algorithm properties¶
- Time complexity: \(O(n \log n)\); not adaptive. On average, partitioning produces \(\log n\) recursive levels, with \(n\) loop iterations in total at each level, giving \(O(n \log n)\) time. In the worst case, each partition splits an array of length \(n\) into subarrays of lengths \(0\) and \(n - 1\). The recursion reaches \(n\) levels, each involving up to \(n\) iterations, for \(O(n^2)\) time overall.
- Space complexity: \(O(n)\); in-place. A fully reverse-sorted input reaches the worst-case recursion depth of \(n\), requiring \(O(n)\) space for stack frames. Sorting takes place in the original array without an auxiliary array.
- Not stable. In the final partitioning step, the pivot may be swapped to the right of an equal element.
11.5.3 Why is quick sort quick?¶
As its name suggests, quick sort has an efficiency advantage. Although its average time complexity matches that of merge sort and heap sort, it is usually faster, mainly for the following reasons.
- The worst case is unlikely. Quick sort's worst-case time complexity is \(O(n^2)\), making its performance less predictable than merge sort's, but it runs in \(O(n \log n)\) time in the vast majority of cases.
- Efficient cache use. During partitioning, the system can load the whole subarray into cache, making element access efficient. Algorithms such as heap sort jump between elements and do not share this advantage.
- Small constant factors. Of these three algorithms, quick sort performs the fewest comparisons, assignments, swaps, and similar operations overall. This resembles the reason insertion sort is faster than bubble sort.
11.5.4 Improving pivot selection¶
Quick sort can become slower on certain inputs. Consider a fully reverse-sorted array. Because the leftmost element is chosen as the pivot, partitioning moves it to the far right, leaving subarrays of lengths \(n - 1\) and \(0\). Continuing recursively produces a subarray of length \(0\) after every partition. Divide and conquer becomes ineffective, and quick sort degenerates into a process resembling bubble sort.
To reduce this risk, we can improve how the pivot is selected. For example, choose a random element as the pivot. With bad luck, however, every pivot may still be poor, leading to disappointing performance.
Programming languages generally produce pseudorandom numbers. A test case constructed specifically for a pseudorandom sequence can still degrade quick sort's performance.
For further improvement, choose three candidate elements, usually the first, last, and middle elements, and use their median as the pivot. This greatly increases the chance that the pivot is neither too small nor too large. We can use more candidates to improve robustness further. This approach greatly reduces the likelihood of degradation to \(O(n^2)\).
An implementation follows:
quick_sort.py
def median_three(self, nums: list[int], left: int, mid: int, right: int) -> int:
"""Select the median of three candidate elements"""
l, m, r = nums[left], nums[mid], nums[right]
if (l <= m <= r) or (r <= m <= l):
return mid # m lies between l and r
if (m <= l <= r) or (r <= l <= m):
return left # l lies between m and r
return right
def partition(self, nums: list[int], left: int, right: int) -> int:
"""Two-pointer partitioning (median of three)"""
# Select the median of the leftmost, middle, and rightmost elements as the pivot
med = self.median_three(nums, left, (left + right) // 2, right)
# Swap the median into the leftmost position of the current subarray
nums[left], nums[med] = nums[med], nums[left]
# Use nums[left] as the pivot
i, j = left, right
while i < j:
while i < j and nums[j] >= nums[left]:
j -= 1 # Scan from right to left for the first element smaller than the pivot
while i < j and nums[i] <= nums[left]:
i += 1 # Scan from left to right for the first element larger than the pivot
# Swap the elements
nums[i], nums[j] = nums[j], nums[i]
# Swap the pivot into the boundary position between the two subarrays
nums[i], nums[left] = nums[left], nums[i]
return i # Return the pivot index
quick_sort.cpp
/* Select the median of three candidate elements */
int medianThree(vector<int> &nums, int left, int mid, int right) {
int l = nums[left], m = nums[mid], r = nums[right];
if ((l <= m && m <= r) || (r <= m && m <= l))
return mid; // m lies between l and r
if ((m <= l && l <= r) || (r <= l && l <= m))
return left; // l lies between m and r
return right;
}
/* Two-pointer partitioning (median of three) */
int partition(vector<int> &nums, int left, int right) {
// Select the median of three candidate elements
int med = medianThree(nums, left, (left + right) / 2, right);
// Swap the median into the leftmost position of the current subarray
swap(nums[left], nums[med]);
// Use nums[left] as the pivot
int i = left, j = right;
while (i < j) {
while (i < j && nums[j] >= nums[left])
j--; // Scan from right to left for the first element smaller than the pivot
while (i < j && nums[i] <= nums[left])
i++; // Scan from left to right for the first element larger than the pivot
swap(nums[i], nums[j]); // Swap these two elements
}
swap(nums[i], nums[left]); // Swap the pivot into the boundary position between the two subarrays
return i; // Return the pivot index
}
quick_sort.java
/* Select the median of three candidate elements */
int medianThree(int[] nums, int left, int mid, int right) {
int l = nums[left], m = nums[mid], r = nums[right];
if ((l <= m && m <= r) || (r <= m && m <= l))
return mid; // m lies between l and r
if ((m <= l && l <= r) || (r <= l && l <= m))
return left; // l lies between m and r
return right;
}
/* Two-pointer partitioning (median of three) */
int partition(int[] nums, int left, int right) {
// Select the median of three candidate elements
int med = medianThree(nums, left, (left + right) / 2, right);
// Swap the median into the leftmost position of the current subarray
swap(nums, left, med);
// Use nums[left] as the pivot
int i = left, j = right;
while (i < j) {
while (i < j && nums[j] >= nums[left])
j--; // Scan from right to left for the first element smaller than the pivot
while (i < j && nums[i] <= nums[left])
i++; // Scan from left to right for the first element larger than the pivot
swap(nums, i, j); // Swap these two elements
}
swap(nums, i, left); // Swap the pivot into the boundary position between the two subarrays
return i; // Return the pivot index
}
quick_sort.cs
/* Select the median of three candidate elements */
int MedianThree(int[] nums, int left, int mid, int right) {
int l = nums[left], m = nums[mid], r = nums[right];
if ((l <= m && m <= r) || (r <= m && m <= l))
return mid; // m lies between l and r
if ((m <= l && l <= r) || (r <= l && l <= m))
return left; // l lies between m and r
return right;
}
/* Two-pointer partitioning (median of three) */
int Partition(int[] nums, int left, int right) {
// Select the median of three candidate elements
int med = MedianThree(nums, left, (left + right) / 2, right);
// Swap the median into the leftmost position of the current subarray
Swap(nums, left, med);
// Use nums[left] as the pivot
int i = left, j = right;
while (i < j) {
while (i < j && nums[j] >= nums[left])
j--; // Scan from right to left for the first element smaller than the pivot
while (i < j && nums[i] <= nums[left])
i++; // Scan from left to right for the first element larger than the pivot
Swap(nums, i, j); // Swap these two elements
}
Swap(nums, i, left); // Swap the pivot into the boundary position between the two subarrays
return i; // Return the pivot index
}
quick_sort.go
/* Select the median of three candidate elements */
func (q *quickSortMedian) medianThree(nums []int, left, mid, right int) int {
l, m, r := nums[left], nums[mid], nums[right]
if (l <= m && m <= r) || (r <= m && m <= l) {
return mid // m lies between l and r
}
if (m <= l && l <= r) || (r <= l && l <= m) {
return left // l lies between m and r
}
return right
}
/* Two-pointer partitioning (median of three)*/
func (q *quickSortMedian) partition(nums []int, left, right int) int {
// Select the median of the left, middle, and right elements as the pivot
med := q.medianThree(nums, left, (left+right)/2, right)
// Swap the median into the leftmost position of the current subarray
nums[left], nums[med] = nums[med], nums[left]
// Use nums[left] as the pivot
i, j := left, right
for i < j {
for i < j && nums[j] >= nums[left] {
j-- //Scan from right to left for the first element smaller than the pivot
}
for i < j && nums[i] <= nums[left] {
i++ //Scan from left to right for the first element larger than the pivot
}
//Swap the elements
nums[i], nums[j] = nums[j], nums[i]
}
//Swap the pivot into the boundary position between the two subarrays
nums[i], nums[left] = nums[left], nums[i]
return i //Return the pivot index
}
quick_sort.swift
/* Select the median of three candidate elements */
func medianThree(nums: [Int], left: Int, mid: Int, right: Int) -> Int {
let l = nums[left]
let m = nums[mid]
let r = nums[right]
if (l <= m && m <= r) || (r <= m && m <= l) {
return mid // m lies between l and r
}
if (m <= l && l <= r) || (r <= l && l <= m) {
return left // l lies between m and r
}
return right
}
/* Two-pointer partitioning (median of three) */
func partitionMedian(nums: inout [Int], left: Int, right: Int) -> Int {
// Select the median of three candidate elements
let med = medianThree(nums: nums, left: left, mid: left + (right - left) / 2, right: right)
// Swap the median into the leftmost position of the current subarray
nums.swapAt(left, med)
return partition(nums: &nums, left: left, right: right)
}
quick_sort.js
/* Select the median of three candidate elements */
medianThree(nums, left, mid, right) {
let l = nums[left],
m = nums[mid],
r = nums[right];
// m lies between l and r
if ((l <= m && m <= r) || (r <= m && m <= l)) return mid;
// l lies between m and r
if ((m <= l && l <= r) || (r <= l && l <= m)) return left;
return right;
}
/* Two-pointer partitioning (median of three) */
partition(nums, left, right) {
// Select the median of three candidate elements
let med = this.medianThree(
nums,
left,
Math.floor((left + right) / 2),
right
);
// Swap the median into the leftmost position of the current subarray
this.swap(nums, left, med);
// Use nums[left] as the pivot
let i = left,
j = right;
while (i < j) {
while (i < j && nums[j] >= nums[left]) j--; // Scan from right to left for the first element smaller than the pivot
while (i < j && nums[i] <= nums[left]) i++; // Scan from left to right for the first element larger than the pivot
this.swap(nums, i, j); // Swap these two elements
}
this.swap(nums, i, left); // Swap the pivot into the boundary position between the two subarrays
return i; // Return the pivot index
}
quick_sort.ts
/* Select the median of three candidate elements */
medianThree(
nums: number[],
left: number,
mid: number,
right: number
): number {
let l = nums[left],
m = nums[mid],
r = nums[right];
// m lies between l and r
if ((l <= m && m <= r) || (r <= m && m <= l)) return mid;
// l lies between m and r
if ((m <= l && l <= r) || (r <= l && l <= m)) return left;
return right;
}
/* Two-pointer partitioning (median of three) */
partition(nums: number[], left: number, right: number): number {
// Select the median of three candidate elements
let med = this.medianThree(
nums,
left,
Math.floor((left + right) / 2),
right
);
// Swap the median into the leftmost position of the current subarray
this.swap(nums, left, med);
// Use nums[left] as the pivot
let i = left,
j = right;
while (i < j) {
while (i < j && nums[j] >= nums[left]) {
j--; // Scan from right to left for the first element smaller than the pivot
}
while (i < j && nums[i] <= nums[left]) {
i++; // Scan from left to right for the first element larger than the pivot
}
this.swap(nums, i, j); // Swap these two elements
}
this.swap(nums, i, left); // Swap the pivot into the boundary position between the two subarrays
return i; // Return the pivot index
}
quick_sort.dart
/* Select the median of three candidate elements */
int _medianThree(List<int> nums, int left, int mid, int right) {
int l = nums[left], m = nums[mid], r = nums[right];
if ((l <= m && m <= r) || (r <= m && m <= l))
return mid; // m lies between l and r
if ((m <= l && l <= r) || (r <= l && l <= m))
return left; // l lies between m and r
return right;
}
/* Two-pointer partitioning (median of three) */
int _partition(List<int> nums, int left, int right) {
// Select the median of three candidate elements
int med = _medianThree(nums, left, (left + right) ~/ 2, right);
// Swap the median into the leftmost position of the current subarray
_swap(nums, left, med);
// Use nums[left] as the pivot
int i = left, j = right;
while (i < j) {
while (i < j && nums[j] >= nums[left]) j--; // Scan from right to left for the first element smaller than the pivot
while (i < j && nums[i] <= nums[left]) i++; // Scan from left to right for the first element larger than the pivot
_swap(nums, i, j); // Swap these two elements
}
_swap(nums, i, left); // Swap the pivot into the boundary position between the two subarrays
return i; // Return the pivot index
}
quick_sort.rs
/* Select the median of three candidate elements */
fn median_three(nums: &mut [i32], left: usize, mid: usize, right: usize) -> usize {
let (l, m, r) = (nums[left], nums[mid], nums[right]);
if (l <= m && m <= r) || (r <= m && m <= l) {
return mid; // m lies between l and r
}
if (m <= l && l <= r) || (r <= l && l <= m) {
return left; // l lies between m and r
}
right
}
/* Two-pointer partitioning (median of three) */
fn partition(nums: &mut [i32], left: usize, right: usize) -> usize {
// Select the median of three candidate elements
let med = Self::median_three(nums, left, (left + right) / 2, right);
// Swap the median into the leftmost position of the current subarray
nums.swap(left, med);
// Use nums[left] as the pivot
let (mut i, mut j) = (left, right);
while i < j {
while i < j && nums[j] >= nums[left] {
j -= 1; // Scan from right to left for the first element smaller than the pivot
}
while i < j && nums[i] <= nums[left] {
i += 1; // Scan from left to right for the first element larger than the pivot
}
nums.swap(i, j); // Swap these two elements
}
nums.swap(i, left); // Swap the pivot into the boundary position between the two subarrays
i // Return the pivot index
}
quick_sort.c
/* Select the median of three candidate elements */
int medianThree(int nums[], int left, int mid, int right) {
int l = nums[left], m = nums[mid], r = nums[right];
if ((l <= m && m <= r) || (r <= m && m <= l))
return mid; // m lies between l and r
if ((m <= l && l <= r) || (r <= l && l <= m))
return left; // l lies between m and r
return right;
}
/* Two-pointer partitioning (median of three) */
int partitionMedian(int nums[], int left, int right) {
// Select the median of three candidate elements
int med = medianThree(nums, left, (left + right) / 2, right);
// Swap the median into the leftmost position of the array
swap(nums, left, med);
// Use nums[left] as the pivot
int i = left, j = right;
while (i < j) {
while (i < j && nums[j] >= nums[left])
j--; // Scan from right to left for the first element smaller than the pivot
while (i < j && nums[i] <= nums[left])
i++; // Scan from left to right for the first element larger than the pivot
swap(nums, i, j); // Swap these two elements
}
swap(nums, i, left); // Swap the pivot into the boundary position between the two subarrays
return i; // Return the pivot index
}
quick_sort.kt
/* Select the median of three candidate elements */
fun medianThree(nums: IntArray, left: Int, mid: Int, right: Int): Int {
val l = nums[left]
val m = nums[mid]
val r = nums[right]
if ((m in l..r) || (m in r..l))
return mid // m lies between l and r
if ((l in m..r) || (l in r..m))
return left // l lies between m and r
return right
}
/* Two-pointer partitioning (median of three) */
fun partitionMedian(nums: IntArray, left: Int, right: Int): Int {
// Select the median of three candidate elements
val med = medianThree(nums, left, (left + right) / 2, right)
// Swap the median into the leftmost position of the current subarray
swap(nums, left, med)
// Use nums[left] as the pivot
var i = left
var j = right
while (i < j) {
while (i < j && nums[j] >= nums[left])
j-- // Scan from right to left for the first element smaller than the pivot
while (i < j && nums[i] <= nums[left])
i++ // Scan from left to right for the first element larger than the pivot
swap(nums, i, j) // Swap these two elements
}
swap(nums, i, left) // Swap the pivot into the boundary position between the two subarrays
return i // Return the pivot index
}
quick_sort.rb
### Select the median of three candidate elements ###
def median_three(nums, left, mid, right)
# Select the median of three candidate elements
_l, _m, _r = nums[left], nums[mid], nums[right]
# _m lies between _l and _r
return mid if (_l <= _m && _m <= _r) || (_r <= _m && _m <= _l)
# _l lies between _m and _r
return left if (_m <= _l && _l <= _r) || (_r <= _l && _l <= _m)
return right
end
### Two-pointer partitioning (median of three)###
def partition(nums, left, right)
### Use nums[left] as the pivot
med = median_three(nums, left, (left + right) / 2, right)
# Swap the median into the leftmost position of the current subarray
nums[left], nums[med] = nums[med], nums[left]
i, j = left, right
while i < j
while i < j && nums[j] >= nums[left]
j -= 1 # Scan from right to left for the first element smaller than the pivot
end
while i < j && nums[i] <= nums[left]
i += 1 # Scan from left to right for the first element larger than the pivot
end
# Swap the elements
nums[i], nums[j] = nums[j], nums[i]
end
# Swap the pivot into the boundary position between the two subarrays
nums[i], nums[left] = nums[left], nums[i]
i # Return the pivot index
end
Visualize execution
11.5.5 Reducing recursion depth¶
Quick sort may use considerable space on certain inputs. For a fully sorted input, let the current subarray have length \(m\). Each partition produces a left subarray of length \(0\) and a right subarray of length \(m - 1\). Each recursive call therefore reduces the problem size by only one element, producing a recursion tree of height \(n - 1\) and requiring \(O(n)\) space for stack frames.
To prevent stack frames from accumulating, compare the two subarray lengths after each partition and recurse only on the shorter one. Since that subarray has length at most \(n / 2\), the recursion depth is at most \(\log n\), reducing the worst-case space complexity to \(O(\log n)\). The code is as follows:
quick_sort.py
def quick_sort(self, nums: list[int], left: int, right: int):
"""Quick sort (recursion depth optimization)"""
# Stop when the subarray has at most one element
while left < right:
# Perform two-pointer partitioning
pivot = self.partition(nums, left, right)
# Apply quick sort to the shorter of the two subarrays
if pivot - left < right - pivot:
self.quick_sort(nums, left, pivot - 1) # Recursively sort the left subarray
left = pivot + 1 # The remaining unsorted range is [pivot + 1, right]
else:
self.quick_sort(nums, pivot + 1, right) # Recursively sort the right subarray
right = pivot - 1 # The remaining unsorted range is [left, pivot - 1]
quick_sort.cpp
/* Quick sort (recursion depth optimization) */
void quickSort(vector<int> &nums, int left, int right) {
// Stop when the subarray has at most one element
while (left < right) {
// Perform two-pointer partitioning
int pivot = partition(nums, left, right);
// Apply quick sort to the shorter of the two subarrays
if (pivot - left < right - pivot) {
quickSort(nums, left, pivot - 1); // Recursively sort the left subarray
left = pivot + 1; // The remaining unsorted range is [pivot + 1, right]
} else {
quickSort(nums, pivot + 1, right); // Recursively sort the right subarray
right = pivot - 1; // The remaining unsorted range is [left, pivot - 1]
}
}
}
quick_sort.java
/* Quick sort (recursion depth optimization) */
void quickSort(int[] nums, int left, int right) {
// Stop when the subarray has at most one element
while (left < right) {
// Perform two-pointer partitioning
int pivot = partition(nums, left, right);
// Apply quick sort to the shorter of the two subarrays
if (pivot - left < right - pivot) {
quickSort(nums, left, pivot - 1); // Recursively sort the left subarray
left = pivot + 1; // The remaining unsorted range is [pivot + 1, right]
} else {
quickSort(nums, pivot + 1, right); // Recursively sort the right subarray
right = pivot - 1; // The remaining unsorted range is [left, pivot - 1]
}
}
}
quick_sort.cs
/* Quick sort (recursion depth optimization) */
void QuickSort(int[] nums, int left, int right) {
// Stop when the subarray has at most one element
while (left < right) {
// Perform two-pointer partitioning
int pivot = Partition(nums, left, right);
// Apply quick sort to the shorter of the two subarrays
if (pivot - left < right - pivot) {
QuickSort(nums, left, pivot - 1); // Recursively sort the left subarray
left = pivot + 1; // The remaining unsorted range is [pivot + 1, right]
} else {
QuickSort(nums, pivot + 1, right); // Recursively sort the right subarray
right = pivot - 1; // The remaining unsorted range is [left, pivot - 1]
}
}
}
quick_sort.go
/* Quick sort (recursion depth optimization)*/
func (q *quickSortTailCall) quickSort(nums []int, left, right int) {
// Stop when the subarray has at most one element
for left < right {
// Perform two-pointer partitioning
pivot := q.partition(nums, left, right)
// Apply quick sort to the shorter of the two subarrays
if pivot-left < right-pivot {
q.quickSort(nums, left, pivot-1) // Recursively sort the left subarray
left = pivot + 1 // The remaining unsorted range is [pivot + 1, right]
} else {
q.quickSort(nums, pivot+1, right) // Recursively sort the right subarray
right = pivot - 1 // The remaining unsorted range is [left, pivot - 1]
}
}
}
quick_sort.swift
/* Quick sort (recursion depth optimization) */
func quickSortTailCall(nums: inout [Int], left: Int, right: Int) {
var left = left
var right = right
// Stop when the subarray has at most one element
while left < right {
// Perform two-pointer partitioning
let pivot = partition(nums: &nums, left: left, right: right)
// Apply quick sort to the shorter of the two subarrays
if (pivot - left) < (right - pivot) {
quickSortTailCall(nums: &nums, left: left, right: pivot - 1) // Recursively sort the left subarray
left = pivot + 1 // The remaining unsorted range is [pivot + 1, right]
} else {
quickSortTailCall(nums: &nums, left: pivot + 1, right: right) // Recursively sort the right subarray
right = pivot - 1 // The remaining unsorted range is [left, pivot - 1]
}
}
}
quick_sort.js
/* Quick sort (recursion depth optimization) */
quickSort(nums, left, right) {
// Stop when the subarray has at most one element
while (left < right) {
// Perform two-pointer partitioning
let pivot = this.partition(nums, left, right);
// Apply quick sort to the shorter of the two subarrays
if (pivot - left < right - pivot) {
this.quickSort(nums, left, pivot - 1); // Recursively sort the left subarray
left = pivot + 1; // The remaining unsorted range is [pivot + 1, right]
} else {
this.quickSort(nums, pivot + 1, right); // Recursively sort the right subarray
right = pivot - 1; // The remaining unsorted range is [left, pivot - 1]
}
}
}
quick_sort.ts
/* Quick sort (recursion depth optimization) */
quickSort(nums: number[], left: number, right: number): void {
// Stop when the subarray has zero or one element
while (left < right) {
// Perform two-pointer partitioning
let pivot = this.partition(nums, left, right);
// Apply quick sort to the shorter of the two subarrays
if (pivot - left < right - pivot) {
this.quickSort(nums, left, pivot - 1); // Recursively sort the left subarray
left = pivot + 1; // The remaining unsorted range is [pivot + 1, right]
} else {
this.quickSort(nums, pivot + 1, right); // Recursively sort the right subarray
right = pivot - 1; // The remaining unsorted range is [left, pivot - 1]
}
}
}
quick_sort.dart
/* Quick sort (recursion depth optimization) */
void quickSort(List<int> nums, int left, int right) {
// Stop when the subarray has at most one element
while (left < right) {
// Perform two-pointer partitioning
int pivot = _partition(nums, left, right);
// Apply quick sort to the shorter of the two subarrays
if (pivot - left < right - pivot) {
quickSort(nums, left, pivot - 1); // Recursively sort the left subarray
left = pivot + 1; // The remaining unsorted range is [pivot + 1, right]
} else {
quickSort(nums, pivot + 1, right); // Recursively sort the right subarray
right = pivot - 1; // The remaining unsorted range is [left, pivot - 1]
}
}
}
quick_sort.rs
/* Quick sort (recursion depth optimization) */
pub fn quick_sort(mut left: i32, mut right: i32, nums: &mut [i32]) {
// Stop when the subarray has at most one element
while left < right {
// Perform two-pointer partitioning
let pivot = Self::partition(nums, left as usize, right as usize) as i32;
// Apply quick sort to the shorter of the two subarrays
if pivot - left < right - pivot {
Self::quick_sort(left, pivot - 1, nums); // Recursively sort the left subarray
left = pivot + 1; // The remaining unsorted range is [pivot + 1, right]
} else {
Self::quick_sort(pivot + 1, right, nums); // Recursively sort the right subarray
right = pivot - 1; // The remaining unsorted range is [left, pivot - 1]
}
}
}
quick_sort.c
/* Quick sort (recursion depth optimization) */
void quickSortTailCall(int nums[], int left, int right) {
// Stop when the subarray has at most one element
while (left < right) {
// Perform two-pointer partitioning
int pivot = partition(nums, left, right);
// Apply quick sort to the shorter of the two subarrays
if (pivot - left < right - pivot) {
// Recursively sort the left subarray
quickSortTailCall(nums, left, pivot - 1);
// The remaining unsorted range is [pivot + 1, right]
left = pivot + 1;
} else {
// Recursively sort the right subarray
quickSortTailCall(nums, pivot + 1, right);
// The remaining unsorted range is [left, pivot - 1]
right = pivot - 1;
}
}
}
quick_sort.kt
/* Quick sort (recursion depth optimization) */
fun quickSortTailCall(nums: IntArray, left: Int, right: Int) {
// Stop when the subarray has at most one element
var l = left
var r = right
while (l < r) {
// Perform two-pointer partitioning
val pivot = partition(nums, l, r)
// Apply quick sort to the shorter of the two subarrays
if (pivot - l < r - pivot) {
quickSort(nums, l, pivot - 1) // Recursively sort the left subarray
l = pivot + 1 // The remaining unsorted range is [pivot + 1, r]
} else {
quickSort(nums, pivot + 1, r) // Recursively sort the right subarray
r = pivot - 1 // The remaining unsorted range is [l, pivot - 1]
}
}
}
quick_sort.rb
### Quick sort (recursion depth optimization)###
def quick_sort(nums, left, right)
# Continue while the subarray contains more than one element
while left < right
# Two-pointer partitioning
pivot = partition(nums, left, right)
# Apply quick sort to the shorter of the two subarrays
if pivot - left < right - pivot
quick_sort(nums, left, pivot - 1)
left = pivot + 1 # The remaining unsorted range is [pivot + 1, right]
else
quick_sort(nums, pivot + 1, right)
right = pivot - 1 # The remaining unsorted range is [left, pivot - 1]
end
end
end