Sorting Algorithms

Sorting algorithms arrange elements in a specific order (ascending, descending, or custom). Understanding sorting is fundamental to algorithm design and helps you appreciate Rust's zero-cost abstractions.

When implementing sorting in Rust, we face:

• Ownership: Who owns the data during sorting?
• In-place vs. allocating: Trade-offs between memory and simplicity
• Generic comparison: Working with any comparable type
• Stability: Preserving relative order of equal elements

use std::cmp::Ordering;

/// QuickSort - efficient average case O(n log n)
pub fn quicksort<T: Ord>(arr: &mut [T]) {
    if arr.len() <= 1 {
        return;
    }

    let pivot_index = partition(arr);

    let (left, right) = arr.split_at_mut(pivot_index);
    quicksort(left);
    quicksort(&mut right[1..]); // Skip the pivot
}

fn partition<T: Ord>(arr: &mut [T]) -> usize {
    let len = arr.len();
    let pivot_index = len / 2;

    // Move pivot to end
    arr.swap(pivot_index, len - 1);

    let mut store_index = 0;
    for i in 0..len - 1 {
        if arr[i] <= arr[len - 1] {
            arr.swap(i, store_index);
            store_index += 1;
        }
    }

    // Move pivot to its final position
    arr.swap(store_index, len - 1);
    store_index
}

/// MergeSort - stable, guaranteed O(n log n)
pub fn mergesort<T: Ord + Clone>(arr: &mut [T]) {
    let len = arr.len();
    if len <= 1 {
        return;
    }

    let mid = len / 2;
    mergesort(&mut arr[..mid]);
    mergesort(&mut arr[mid..]);

    // Merge the two halves
    let merged = merge(&arr[..mid], &arr[mid..]);
    arr.clone_from_slice(&merged);
}

fn merge<T: Ord + Clone>(left: &[T], right: &[T]) -> Vec<T> {
    let mut result = Vec::with_capacity(left.len() + right.len());
    let mut left_iter = left.iter().peekable();
    let mut right_iter = right.iter().peekable();

    loop {
        match (left_iter.peek(), right_iter.peek()) {
            (Some(l), Some(r)) => {
                if l <= r {
                    result.push((*left_iter.next().unwrap()).clone());
                } else {
                    result.push((*right_iter.next().unwrap()).clone());
                }
            }
            (Some(_), None) => {
                result.extend(left_iter.cloned());
                break;
            }
            (None, Some(_)) => {
                result.extend(right_iter.cloned());
                break;
            }
            (None, None) => break,
        }
    }

    result
}

/// HeapSort - in-place, O(n log n) guaranteed
pub fn heapsort<T: Ord>(arr: &mut [T]) {
    let len = arr.len();
    if len <= 1 {
        return;
    }

    // Build max heap
    for i in (0..len / 2).rev() {
        heapify(arr, len, i);
    }

    // Extract elements from heap
    for i in (1..len).rev() {
        arr.swap(0, i);
        heapify(arr, i, 0);
    }
}

fn heapify<T: Ord>(arr: &mut [T], heap_size: usize, root: usize) {
    let mut largest = root;
    let left = 2 * root + 1;
    let right = 2 * root + 2;

    if left < heap_size && arr[left] > arr[largest] {
        largest = left;
    }
    if right < heap_size && arr[right] > arr[largest] {
        largest = right;
    }

    if largest != root {
        arr.swap(root, largest);
        heapify(arr, heap_size, largest);
    }
}

/// InsertionSort - efficient for small arrays, stable
pub fn insertion_sort<T: Ord>(arr: &mut [T]) {
    for i in 1..arr.len() {
        let mut j = i;
        while j > 0 && arr[j - 1] > arr[j] {
            arr.swap(j - 1, j);
            j -= 1;
        }
    }
}

/// Generic sort with custom comparator
pub fn sort_by<T, F>(arr: &mut [T], compare: F)
where
    F: Fn(&T, &T) -> Ordering,
{
    // Using insertion sort for simplicity; production code would use introsort
    for i in 1..arr.len() {
        let mut j = i;
        while j > 0 && compare(&arr[j - 1], &arr[j]) == Ordering::Greater {
            arr.swap(j - 1, j);
            j -= 1;
        }
    }
}

/// Sort by key extraction
pub fn sort_by_key<T, K, F>(arr: &mut [T], key: F)
where
    K: Ord,
    F: Fn(&T) -> K,
{
    sort_by(arr, |a, b| key(a).cmp(&key(b)));
}

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

    // MergeSort
    let mut arr2 = vec![64, 34, 25, 12, 22, 11, 90];
    mergesort(&mut arr2);
    println!("MergeSort: {:?}", arr2);

    // HeapSort
    let mut arr3 = vec![64, 34, 25, 12, 22, 11, 90];
    heapsort(&mut arr3);
    println!("HeapSort: {:?}", arr3);

    // Custom comparator - sort descending
    let mut arr4 = vec![64, 34, 25, 12, 22, 11, 90];
    sort_by(&mut arr4, |a, b| b.cmp(a));
    println!("Descending: {:?}", arr4);

    // Sort by key
    let mut people = vec![
        ("Alice", 30),
        ("Bob", 25),
        ("Charlie", 35),
    ];
    sort_by_key(&mut people, |p| p.1); // Sort by age
    println!("By age: {:?}", people);
}

1. &mut [T]: Sorting operates on slices, borrowing mutably
2. split_at_mut: Safely splits slice for recursive operations
3. T: Ord: Generic constraint ensures comparability
4. T: Clone: MergeSort needs cloning for stable merging

| Algorithm | Time (avg) | Time (worst) | Space | Stable |

|-----------|------------|--------------|-------|--------|

| QuickSort | O(n log n) | O(n²) | O(log n) | No |

| MergeSort | O(n log n) | O(n log n) | O(n) | Yes |

| HeapSort | O(n log n) | O(n log n) | O(1) | No |

| InsertionSort | O(n²) | O(n²) | O(1) | Yes |

fn main() {
    let mut nums = vec![3, 1, 4, 1, 5, 9, 2, 6];

    // Unstable sort (faster, no stability guarantee)
    nums.sort_unstable();

    // Stable sort
    nums.sort();

    // Custom comparator
    nums.sort_by(|a, b| b.cmp(a)); // Descending

    // Sort by key
    let mut words = vec!["apple", "pie", "a"];
    words.sort_by_key(|s| s.len());

    // Parallel sort with rayon
    // nums.par_sort_unstable();
}

| Algorithm | Use When |

|-----------|----------|

| sort_unstable() | Default choice, fastest |

| sort() | Need stability (equal elements keep order) |

| QuickSort | Learning, or when you need control |

| MergeSort | External sorting, linked lists |

| HeapSort | Memory-constrained, need guaranteed O(n log n) |

| InsertionSort | Small arrays, nearly sorted data |

1. Implement radix sort for integers
2. Add a is_sorted() check function
3. Implement tim sort (hybrid of merge + insertion)
4. Write a parallel quicksort using rayon