Quick Sort
O(n log n)

History

Quick Sort was developed by Tony Hoare in 1959 and published in 1961. It's often the fastest sorting algorithm in practice. The algorithm works by selecting a 'pivot' element and partitioning the array around it, placing smaller elements before and larger elements after. Despite its O(n²) worst case, careful pivot selection (like median-of-three) makes this scenario extremely rare in practice.

How it works

Choose a pivot element
Partition: place smaller elements left, larger right
Recursively sort the left partition
Recursively sort the right partition

When to use

General-purpose sorting: Fastest on average
Arrays: Excellent cache performance
When stability not needed: Many practical applications
Large datasets: Scales well with size

💡 Used as the default sort in C, Java, and many other languages

Implementation

def quick_sort(arr):
    if len(arr) <= 1:
        return arr
    pivot = arr[len(arr) // 2]
    left = [x for x in arr if x < pivot]
    middle = [x for x in arr if x == pivot]
    right = [x for x in arr if x > pivot]
    return quick_sort(left) + middle + quick_sort(right)

function quickSort(arr) {
    if (arr.length <= 1) return arr;
    const pivot = arr[Math.floor(arr.length / 2)];
    const left = arr.filter(x => x < pivot);
    const middle = arr.filter(x => x === pivot);
    const right = arr.filter(x => x > pivot);
    return [...quickSort(left), ...middle, ...quickSort(right)];
}

func quickSort(arr []int) []int {
    if len(arr) <= 1 {
        return arr
    }
    pivot := arr[len(arr)/2]
    var left, middle, right []int
    for _, x := range arr {
        switch {
        case x < pivot:
            left = append(left, x)
        case x == pivot:
            middle = append(middle, x)
        default:
            right = append(right, x)
        }
    }
    result := quickSort(left)
    result = append(result, middle...)
    result = append(result, quickSort(right)...)
    return result
}

fn quick_sort<T: Ord + Clone>(arr: &[T]) -> Vec<T> {
    if arr.len() <= 1 {
        return arr.to_vec();
    }
    let pivot = arr[arr.len() / 2].clone();
    let left: Vec<_> = arr.iter().filter(|x| **x < pivot).cloned().collect();
    let middle: Vec<_> = arr.iter().filter(|x| **x == pivot).cloned().collect();
    let right: Vec<_> = arr.iter().filter(|x| **x > pivot).cloned().collect();
    [quick_sort(&left), middle, quick_sort(&right)].concat()
}