Sorting

Quick Sort (Lomuto)

Choose the last item as a pivot, partition smaller values to its left, then recurse on the two sides.

Algorithm

Basic Implementation

basic.rs 
fn partition(arr: &mut [i32], low: usize, high: usize) -> usize {
	let pivot = arr[high];
	let mut i = low;
	for j in low..high {
		if arr[j] <= pivot {
			arr.swap(i, j);
			i += 1;
		}
	}
	arr.swap(i, high);
	i
}

fn quick_sort(arr: &mut [i32], low: usize, high: usize) {
	if low < high {
		let pivot_index = partition(arr, low, high);
		if pivot_index > 0 {
			quick_sort(arr, low, pivot_index - 1);
		}
		quick_sort(arr, pivot_index + 1, high);
	}
}

fn main() {
	let mut arr = [4, 1, 5, 2, 3];
	let last = arr.len() - 1;
	quick_sort(&mut arr, 0, last);
	println!("{:?}", arr);
}

The pinned first partition uses [4, 1, 5, 2, 3] with pivot 3. The diagrams track the boundary, swaps, and recursive ranges.

Step 1 - Choose the last value as pivot

The pivot is arr[4] = 3, and i starts just before the current range.

Initial partition state for [4, 1, 5, 2, 3].i0i1i2i3i441523j startspivot

Step 2 - Swap small values left

1 and 2 are <= pivot, so they move into the left partition.

After scanning values before the pivot: [1, 2, 5, 4, 3].i0i1i2i3i412543<= 3<= 3> 3> 3pivot

Step 3 - Place pivot, then recurse

Swapping pivot 3 into index 2 gives [1, 2, 3, 4, 5]; recurse on [1, 2] and [4, 5].

Pivot lands at index 2 and splits the remaining work.left rangepivotright range[1, 2]3 at i2[4, 5]quick_sort(0,1)fixedquick_sort(3,4)

Complexity

  • Time: O(n^2) worst, O(n log n) average
  • Space: O(log n) average call stack
  • Stable: no

Implementation notes

  • The checked source uses a fixed mutable array, let mut arr = [4, 1, 5, 2, 3], and passes it as &mut [i32]; it does not allocate a Vec.
  • partition(arr: &mut [i32], low: usize, high: usize) -> usize receives the mutable slice plus bounds, chooses pivot = arr[high], and returns the final pivot index.
  • quick_sort(arr: &mut [i32], low: usize, high: usize) mutates in place and returns (). It recurses only when low < high.
  • The source keeps i as the next left-side write slot and scans for j in low..high. On arr[j] <= pivot, arr.swap(i, j) moves that value left and then increments i.
  • After the scan, arr.swap(i, high) places the pivot. The recursive left call is guarded by if pivot_index > 0 so pivot_index - 1 cannot underflow as a usize.
  • The trace records the first partition around pivot 3: keep 4, swap 1 left, keep 5, swap 2 left, then swap the pivot into index 2, yielding [1, 2, 3, 4, 5]. Its i labels the left boundary, while the Rust variable holds the next write slot.
  • Recursive calls on [1, 2] and [4, 5] are summarized in the trace. The final println!("{:?}", arr) uses debug formatting and prints [1, 2, 3, 4, 5].
pivot The final element is moved to the boundary between smaller and larger values.
partition One scan rearranges the current range before the recursive calls.