Quick3 Sort
O(n log n)

History

Quick3 Sort (3-way Quick Sort) is a variation developed by Dijkstra for handling arrays with many duplicate keys. Instead of two partitions, it creates three: elements less than, equal to, and greater than the pivot. This variant was later improved by Bentley and McIlroy (1993) and is now the default sorting algorithm in many standard libraries when duplicates are common.

How it works

Choose a pivot element
Partition into three: less than, equal to, greater than pivot
Recursively sort the 'less than' partition
Recursively sort the 'greater than' partition
Elements equal to pivot are already in place

When to use

Many duplicate keys: Linear time for all equal elements
Limited key range: Like sorting grades or categories
String sorting: Common prefixes are handled efficiently
General-purpose: As good as Quick Sort, better with duplicates

Implementation

def quick3_sort(arr, lo=0, hi=None):
    if hi is None:
        hi = len(arr) - 1
    if lo >= hi:
        return arr
    lt, gt = lo, hi
    pivot = arr[lo]
    i = lo + 1
    while i <= gt:
        if arr[i] < pivot:
            arr[lt], arr[i] = arr[i], arr[lt]
            lt += 1
            i += 1
        elif arr[i] > pivot:
            arr[gt], arr[i] = arr[i], arr[gt]
            gt -= 1
        else:
            i += 1
    quick3_sort(arr, lo, lt - 1)
    quick3_sort(arr, gt + 1, hi)
    return arr

function quick3Sort(arr, lo = 0, hi = arr.length - 1) {
    if (lo >= hi) return arr;
    let lt = lo, gt = hi, i = lo + 1;
    const pivot = arr[lo];
    while (i <= gt) {
        if (arr[i] < pivot) {
            [arr[lt], arr[i]] = [arr[i], arr[lt]];
            lt++; i++;
        } else if (arr[i] > pivot) {
            [arr[gt], arr[i]] = [arr[i], arr[gt]];
            gt--;
        } else {
            i++;
        }
    }
    quick3Sort(arr, lo, lt - 1);
    quick3Sort(arr, gt + 1, hi);
    return arr;
}

func quick3Sort(arr []int, lo, hi int) {
    if lo >= hi {
        return
    }
    lt, gt, i := lo, hi, lo+1
    pivot := arr[lo]
    for i <= gt {
        switch {
        case arr[i] < pivot:
            arr[lt], arr[i] = arr[i], arr[lt]
            lt++
            i++
        case arr[i] > pivot:
            arr[gt], arr[i] = arr[i], arr[gt]
            gt--
        default:
            i++
        }
    }
    quick3Sort(arr, lo, lt-1)
    quick3Sort(arr, gt+1, hi)
}

fn quick3_sort<T: Ord>(arr: &mut [T]) {
    if arr.len() <= 1 { return; }
    let (mut lt, mut gt, mut i) = (0, arr.len() - 1, 1);
    while i <= gt {
        match arr[i].cmp(&arr[lt]) {
            std::cmp::Ordering::Less => {
                arr.swap(lt, i);
                lt += 1;
                i += 1;
            }
            std::cmp::Ordering::Greater => {
                arr.swap(i, gt);
                gt -= 1;
            }
            std::cmp::Ordering::Equal => i += 1,
        }
    }
    quick3_sort(&mut arr[..lt]);
    if gt + 1 < arr.len() {
        quick3_sort(&mut arr[gt + 1..]);
    }
}