Problem overview
The function sort takes a mutable reference to a vector of integers, nums: &mut Vec<i32>, and sorts it in ascending order, in place, using Quick Sort. It returns nothing: the caller's vector is the result. The lesson states an O(n log n) time target and O(log n) extra space.
For nums = [3, 1, 3, 2, 5, 4] the vector becomes [1, 2, 3, 3, 4, 5].
Approach: partition around a pivot, then sort each side
Quick Sort picks one element, the pivot, and rearranges the range so that everything less than or equal to the pivot is on its left and everything larger is on its right. This step is called partitioning. After it, the pivot is already in its final sorted position. What remains is two smaller, independent problems: sort the part left of the pivot and the part right of it.
Unlike Merge Sort, there is no merge step and no extra buffer: the partition rearranges the elements by swapping them inside the vector.
This version uses the last element of the range as the pivot and walks over the range once. A counter, correct_index, marks where the next element that is less than or equal to the pivot belongs. Everything before correct_index is already less than or equal to the pivot. Whenever the scan finds such an element, it swaps it into correct_index and moves that marker forward.
The scan includes the last position, the pivot itself. Since the pivot is less than or equal to itself, it is swapped into the last slot of the left part, which means it ends at correct_index - 1 and that is the index the function returns.
A small trace
Take the range [3, 1, 3, 2, 5, 4]. The pivot is 4 and correct_index is 0. The elements 3, 1, 3 and 2 are all at most 4, and each swaps with itself while the marker moves to 4. The 5 is larger and is skipped. The final 4, the pivot, swaps with the 5. The vector is [3, 1, 3, 2, 4, 5] and the function returns 4. The left part [3, 1, 3, 2] and the right part [5] are sorted recursively.
Step by step
The entry point sort
- Store the length in
n. - Guard with
n > 1. Only then callSelf::quick_sort(nums, 0, n - 1). For an empty vector,n - 1would underflow ausize.numsis already a mutable reference, so it is passed on as it is.
The recursive quick_sort
- Declare it with
nums: &mut Vec<i32>and inclusiveusizeboundsleftandright. - Base case. If
left >= right, the part has at most one element and is sorted. Return. - Partition with
Self::partitionand keep the pivot's final index inpivot. - Sort the left part,
lefttopivot - 1, but only whenpivot > left. Otherwise the left part is empty andpivot - 1would underflow whenpivotis 0. - Sort the right part,
pivot + 1toright. This needs no guard: whenpivotequalsright, the call getsleft > rightand hits the base case.
The helper partition
- Declare it with the same three parameters, returning a
usize. - Save the pivot value,
nums[right], invalue. - Start the marker:
let mut correct_index = left;. - Scan with
for i in left..=right. The..=includesrighton purpose. - Swap small elements into place. If
nums[i] <= value, callnums.swap(i, correct_index)and add one tocorrect_index. - Return
correct_index - 1as the final expression.
The solution in Rust
impl Solution {
fn partition(nums: &mut Vec<i32>, left: usize, right: usize) -> usize {
let value = nums[right];
let mut correct_index = left;
for i in left..=right {
if nums[i] <= value {
nums.swap(i, correct_index);
correct_index += 1;
}
}
correct_index - 1
}
fn quick_sort(nums: &mut Vec<i32>, left: usize, right: usize) {
if left >= right {
return;
}
let pivot = Self::partition(nums, left, right);
if pivot > left {
Self::quick_sort(nums, left, pivot - 1);
}
Self::quick_sort(nums, pivot + 1, right);
}
fn sort(nums: &mut Vec<i32>) {
let n = nums.len();
if n > 1 {
Self::quick_sort(nums, 0, n - 1);
}
}
}
The Rust details worth a closer look:
swapinstead of two assignments. Writinglet t = nums[i]; nums[i] = nums[j]; nums[j] = t;works fori32, butnums.swap(i, j)is shorter and also works for types that can't be copied. The borrow checker wouldn't allow holding two mutable references into the vector at once, which is why the standard library offersswap.- Passing a mutable reference along. Inside the functions,
numsis already a&mut Vec<i32>, soSelf::partition(nums, left, right)passes it on. Rust lends it to the callee for the duration of the call and gives it back afterwards, sonumsis still usable on the next line. - Why
correct_index - 1is safe. The pivot itself passes the testnums[i] <= value, socorrect_indexis at leastleft + 1when the loop ends, and subtracting 1 can't underflow. - Unsigned bounds.
usizecan't hold-1, which is why the left recursion is guarded withpivot > left. In an optimized build0usize - 1would wrap to a huge number, and in a debug build it would panic. - The function returns nothing.
sortandquick_sorthave no->part. They change the vector the caller owns.
Complexity
Time. A partition of a range of m elements does m comparisons. If the pivot lands near the middle every time, the ranges halve and there are about log n levels, so the total is O(n log n). That is the typical case: on a shuffled vector of 1000 numbers the partitions made about 11,600 comparisons.
The weakness of using the last element as the pivot is input that is already sorted, sorted in reverse, or made of equal values. The pivot then ends at one end of the range, one side is empty, and the other side shrinks by just one element each time. That is O(n^2): a vector of 1000 numbers in order takes 500,499 comparisons, the same as 1000 reversed or 1000 equal numbers. Choosing a random pivot, or the median of three elements, avoids this.
Space. Nothing is allocated, but the recursion uses stack frames. With balanced splits the depth is about log n, giving the O(log n) in the statement. In the bad cases above the depth reaches about n. A vector of 1000 sorted numbers goes 999 calls deep, and a much longer one could exhaust the stack.
Edge cases and common mistakes
- Empty and one-element vectors.
sortskips the work because of then > 1check, and the vector is unchanged. - Duplicates.
[2, 2, 2, 1]becomes[1, 2, 2, 2]. Using<=in the partition sends equal elements to the left part, and the scan still terminates. - Quick Sort isn't stable. The swaps can change the relative order of equal elements. It doesn't matter for plain integers.
- Scanning only to
right - 1. The loop uses..=deliberately. Stopping before the pivot would require a separate final swap. - Forgetting the
pivot > leftguard. When the pivot is at index 0,pivot - 1underflows. A debug build panics at the subtraction, and an optimized build wraps to a huge bound and panics on an out-of-range index. - Recursing on
pivotinstead ofpivot - 1orpivot + 1. The pivot is already in place. Including it can make a range stop shrinking, so the recursion never ends.
Testing
[3, 1, 3, 2, 5, 4]becomes[1, 2, 3, 3, 4, 5].[]stays[].[0]stays[0].[2, 2, 2, 1]becomes[1, 2, 2, 2].[5, 4, 3, 2, 1]becomes[1, 2, 3, 4, 5].[-3, 10, -7, 0, 10]becomes[-7, -3, 0, 10, 10].
