Image source: Wikipedia

Algorithm:

1. Choose a pivot element.
2. Move all values less than the pivot to one side and those greater to the other.
3. Recursively sort the two partitions.

Average time complexity: $O(n*log(n))$

Rust implementation:

fn main()
{
    let mut numbers = [9, 2, 3, 5, 1, 7, 0];
    quick_sort(&mut numbers);
    println!("{:?}", numbers);
}

/// Sort `numbers` in place.
fn quick_sort(numbers: &mut [i32])
{
    let size = numbers.len();
    if size < 2
    {
        return;
    }
    let pivot = numbers[0];
    let mut left = 1;
    let mut right = numbers.len() - 1;
    while left <= right
    {
        if numbers[left] < pivot
        {
            left += 1;
        }
        else if numbers[right] > pivot
        {
            right -= 1;
        }
        else
        {
            numbers.swap(left, right);
        }
    }
    numbers.swap(right, 0);
    quick_sort(&mut numbers[0..=right]);
    quick_sort(&mut numbers[left..size]);
}