Quick Sort

Quick sort is a powerful divide-and-conquer algorithm that works by selecting a pivot, partitioning the array around that pivot, and then recursively sorting the subarrays. Its average-case performance is excellent, making it one of the most widely used sorting algorithms in practice. Quick sort is typically faster than merge sort in real-world scenarios due to better cache locality and in-place partitioning.

Example Walk-through

Let’s sort this array:

[10, 7, 8, 9, 1, 5]

We’ll use the last element as the pivot for simplicity.

Step 1 - Partition around pivot = 5

Elements less than 5 go to the left; elements greater go to the right.

Partition result:

[1]   [5]   [10, 7, 8, 9]

Pivot 5 is now in its final, correct position.

Step 2 - Recursively sort left side

Left side: [1] Already sorted.

Step 3 - Recursively sort right side

Right side: [10, 7, 8, 9] Pivot = 9

Partition:

[7, 8]   [9]   [10]

Now sort each part:

• [7, 8] pivot = 8 → [7] [8]
• [10] already sorted

Final sorted array:

[1, 5, 7, 8, 9, 10]

Quick sort is efficient because most of the work happens during partitioning, and well-chosen pivots keep recursion depth small.

Rust Implementation

This version uses the Lomuto partition scheme for clarity. It sorts the slice in-place and recursively sorts the subranges.

pub fn quick_sort(arr: &mut [i32]) {
    let len = arr.len();
    if len > 1 {
        quick_sort_recursive(arr, 0, (len - 1) as isize);
    }
}

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

fn partition(arr: &mut [i32], low: isize, high: isize) -> isize {
    let pivot = arr[high as usize];
    let mut i = low - 1;

    for j in low..high {
        if arr[j as usize] <= pivot {
            i += 1;
            arr.swap(i as usize, j as usize);
        }
    }

    // Place pivot in correct position
    arr.swap((i + 1) as usize, high as usize);
    i + 1
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn it_sorts() {
        let mut input = vec![10, 7, 8, 9, 1, 5];
        quick_sort(&mut input);
        assert_eq!(input, vec![1, 5, 7, 8, 9, 10]);
    }
}

Example Usage

fn main() {
    let mut values = vec![64, 34, 25, 12, 22, 11, 90];
    quick_sort(&mut values);
    println!("{:?}", values); // [11, 12, 22, 25, 34, 64, 90]
}

Time and Space Complexity

Quick sort’s performance heavily depends on pivot selection.

Space Complexity

Worst case recursion depth is O(n), but this is uncommon unless pivots are chosen poorly.

Playground Links

Rust - Quick Sort