Problem overview
The method Sort receives an int[] named nums and must sort it in ascending order with Quick Sort, in place. For nums = [3, 1, 3, 2, 5, 4] the array becomes [1, 2, 3, 3, 4, 5].
The lesson asks for O(n log n) time and O(log n) extra space. Unlike Merge Sort, Quick Sort needs no second array: it rearranges the values inside nums itself.
Approach: partition around a pivot, then sort each side
Quick Sort picks one value, the pivot, and partitions the range: every value less than or equal to the pivot ends up before it, and every larger value ends up after it. After that single pass the pivot is in its final sorted position, and it never moves again. What remains is two smaller, independent problems: sort the part before the pivot, and sort the part after it.
The speed depends on how even the split is. A pivot near the middle halves the problem, giving about log n levels of work with O(n) per level. A pivot that is always the smallest or largest value peels off one element per pass and costs O(n²). A fixed choice such as "always the last element" is exactly that on input that is already sorted, so this lesson picks the pivot at random. A random pivot makes the bad splits unlikely whatever the input looks like, and the running time of O(n log n) holds in expectation.
Here is one partition of [3, 1, 3, 2, 5, 4] when the random choice happens to be the value 4. It is already at the end. Scanning from the left, 3, 1, 3 and 2 are all at most 4, so each stays where it is while the boundary index moves right. The 5 is larger and is skipped. Finally 4 itself is at most 4 and is swapped with the 5, giving [3, 1, 3, 2, 4, 5]. The pivot's index is 4. The left part [3, 1, 3, 2] and the right part [5] are then sorted recursively.
Step by step
- Start the recursion.
QuickSort(nums, 0, nums.Length - 1)sorts the whole array. The bounds are inclusive. - Declare
QuickSort. It takes the array and the two bounds. Arrays are passed by reference, so the caller sees the changes. - Base case. If
left >= right, the part has at most one element and is already sorted. - Partition.
Partitionrearranges the part and returns the pivot's final index, stored inpivot. - Recurse on both sides. The left part is
lefttopivot - 1and the right part ispivot + 1toright. The pivot is excluded because it is already in place. - Write
Partition. It has the same parameters and returns anint. - Pick a random index between
leftandright, both included, and swap that element to the end of the part, so the scan below can walk past all the other elements without stepping over the pivot. - Remember the pivot value in
value, and startcorrectIndexatleft. It marks where the next value that is at mostvaluebelongs; everything before it already qualifies. - Scan from
lefttoright, inclusive. Whenevernums[i] <= value, swap it into positioncorrectIndexand advancecorrectIndex. Includingrightis deliberate: the pivot itself passes the test and is swapped into place last. - Return
correctIndex - 1. The pivot was the last value moved into the "small" region, so it sits just beforecorrectIndex. - Write
Swap. It exchanges two elements through a temporary variable, because the first assignment would otherwise overwrite a value that is still needed.
The solution in C#
class Solution {
public void Swap(int[] nums, int i, int j) {
int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}
public int Partition(int[] nums, int left, int right) {
int randomIndex = left + (int)(new Random().NextDouble() * (right - left + 1));
Swap(nums, randomIndex, right);
int value = nums[right];
int correctIndex = left;
for (int i = left; i <= right; ++i) {
if (nums[i] <= value) {
Swap(nums, i, correctIndex);
correctIndex++;
}
}
return correctIndex - 1;
}
public void QuickSort(int[] nums, int left, int right) {
if (left >= right) {
return;
}
int pivot = Partition(nums, left, right);
QuickSort(nums, left, pivot - 1);
QuickSort(nums, pivot + 1, right);
}
public void Sort(int[] nums) {
QuickSort(nums, 0, nums.Length - 1);
}
}
The C# details worth a closer look:
- The random index.
NextDouble()returns adoublefrom 0 up to but not including 1. Multiplying byright - left + 1gives a value from 0 up to but not including that size, and the(int)cast drops the fraction, so the offset is a whole number from0toright - left. Addingleftplaces it inside the range.Random.Shared.Next(left, right + 1)does the same job directly; its upper bound is exclusive. - A new
Randomeach time. Without a seed argument, everynew Random()gets its own seed, so this is fine in current .NET, although a shared instance is the more usual style. - Methods can call each other in any order.
PartitionusesSwapwithout anythis., and the order of the methods in the class doesn't matter in C#. - Passing the array.
Swapmodifies the same array object thatSortreceived, so nothing needs to be returned. ++iandi++. In aforloop's last clause they behave the same, because the value of the expression isn't used.
Complexity
Time: O(n log n) expected. Each partition scans its range once, which is linear in the range's size. With a random pivot, the expected recursion depth is proportional to log n, and every level of the recursion scans at most n elements in total. The worst case is still O(n²), but a random pivot makes it very unlikely on any input.
Space: O(log n) expected. Nothing is allocated except a few local variables. The only memory that grows is the call stack, whose depth is about log n when the splits are reasonably even.
Edge cases and common mistakes
- Empty and one-element arrays. For an empty array the first call is
QuickSort(nums, 0, -1), and0 >= -1is true, so it returns immediately. The check is>=rather than==for this reason. - Many equal values. Because the test is
<=, every copy of the pivot value moves to the small side. When all values are equal, the pivot index is alwaysright, so each call peels off a single element: the work becomes quadratic and the recursion aboutncalls deep. Typical inputs are fine, but a huge array of identical values would be slow, and it could exhaust the stack. - Recursing on the pivot. Sorting
lefttopivotinstead oflefttopivot - 1would not shrink the range when the pivot is the last element, and the recursion would never end. - Skipping the swap to the end. If the random pivot stays in the middle, the scan swaps it around while it is still being compared against, and the returned index is wrong.
- Scanning only to
right - 1. Then the pivot never reaches its place, and the finalcorrectIndex - 1points at the wrong element. - An off-by-one in the random range. Multiplying by
right - leftinstead ofright - left + 1can never choose the last position.
Testing
[3, 1, 3, 2, 5, 4]becomes[1, 2, 3, 3, 4, 5].- An empty array and
[9]come back unchanged. - Sorted, reversed and all-equal arrays all end up sorted. The random pivot is what keeps the sorted and reversed cases from degrading.