Imagine you're standing in a mailroom with a massive, disorganized pile of printed invoices that need to be filed by date. You can't just magically snap your fingers and have them sorted; you have to physically move them. If you pick one invoice at random and say, "Everything older than this goes in a pile to my left, and everything newer goes to my right," you've just performed the core logic of a Quick Sort. If instead, you split the pile exactly in half, then split those halves again until you're holding single sheets of paper, and then carefully zip them back together in order, you're doing a Merge Sort.

In Rust, we translate these physical movements into slice manipulations. We aren't just moving "paper"; we're manipulating memory addresses and swapping elements within a contiguous block of data. While you'll almost always use slice::sort() or slice::sort_unstable() in a real project, implementing these yourself is the best way to understand how Rust handles generics and mutable borrowing.

The Pivot Strategy with Quick Sort

Quick Sort is all about the "partition." We pick a pivot element and rearrange the slice so that everything smaller than the pivot is on one side and everything larger is on the other. I like Quick Sort because it happens "in-place," meaning we aren't allocating new vectors every time we recurse—we're just swapping elements around in the original slice.

fn quick_sort<T: PartialOrd>(slice: &mut [T]) {
    if slice.len() <= 1 {
        return;
    }

    let pivot_index = partition(slice);
    let (left, right) = slice.split_at_mut(pivot_index);
    
    // We sort the left side, and the right side (excluding the pivot itself)
    quick_sort(left);
    quick_sort(&mut right[1..]);
}

fn partition<T: PartialOrd>(slice: &mut [T]) -> usize {
    let pivot_index = 0;
    let mut i = 1;
    
    for j in 1..slice.len() {
        if slice[j] < slice[pivot_index] {
            slice.swap(i, j);
            i += 1;
        }
    }
    
    slice.swap(pivot_index, i - 1);
    i - 1
}

Notice the T: PartialOrd bound. Since we're using the < operator, we have to tell Rust that the type T actually supports comparison. I used split_at_mut here because Rust's borrow checker won't let you have two mutable references to the same slice. By splitting the slice into two non-overlapping parts, we satisfy the compiler that we aren't accidentally mutating the same element from two different recursive calls.

Divide, Conquer, and Stitch with Merge Sort

Merge Sort is different. It's more predictable than Quick Sort (it doesn't have a "worst-case" scenario where it slows down significantly), but it requires extra memory. Think of it as the "tidy" approach: split everything down to the smallest possible unit, then merge them back together. Because we can't easily "merge" two halves of a slice in-place without a lot of complex shifting, we usually allocate a temporary vector to hold the results.

fn merge_sort<T: PartialOrd + Clone>(slice: &mut [T]) {
    let mid = slice.len() / 2;
    if mid == 0 {
        return;
    }

    merge_sort(&mut slice[..mid]);
    merge_sort(&mut slice[mid..]);

    let mut merged = Vec::with_capacity(slice.len());
    let mut left = 0;
    let mut right = mid;

    while left < mid && right < slice.len() {
        if slice[left] <= slice[right] {
            merged.push(slice[left].clone());
            left += 1;
        } else {
            merged.push(slice[right].clone());
            right += 1;
        }
    }

    merged.extend_from_slice(&slice[left..mid]);
    merged.extend_from_slice(&slice[right..]);
    
    slice.clone_from_slice(&merged);
}

You'll see I added the Clone trait bound here. Since we're pushing elements into a temporary Vec and then copying them back into the original slice, we need to be able to duplicate the data. This is the trade-off: Merge Sort gives you a guaranteed time complexity of O(n log n), but it costs you more in terms of memory allocation.

Picking the Right Tool for the Job

When you're deciding between these in a theoretical sense (or when interviewing), remember that Quick Sort is generally faster in practice because it's cache-friendly and avoids allocations. However, it's unstable—meaning if you have two elements with the same value, their relative order might change. Merge Sort is stable. If you were sorting a list of users by "Last Name" and then by "First Name," stability ensures that your first sort isn't completely ruined by the second one.

📋 Practical Task

Implementation Challenge: Sorting Semantic Version Strings

In real software engineering, we rarely sort simple integers. Often, we have to sort complex strings like version numbers (e.g., "1.2.1", "1.10.0", "2.0.1"). A standard string sort would put "1.10.0" before "1.2.1" because '1' comes before '2' alphabetically, which is incorrect for versioning.

Your task is to implement a custom sorting function using the Quick Sort logic from this lesson, but with a twist: you must implement a custom comparison helper that splits the version strings by the dot (.) and compares the resulting numeric segments as integers.

Requirements:

• Create a function version_sort(versions: &mut Vec<String>).
• Implement a helper function compare_versions(a: &str, b: &str) -> std::cmp::Ordering that correctly identifies that "1.10.0" is greater than "1.2.1".
• Modify the partition logic from the lesson to use your compare_versions helper instead of the < operator.
• Test it with a list containing: ["1.0.0", "1.10.0", "1.2.1", "2.1.0", "2.0.9"]. The final order should be ["1.0.0", "1.2.1", "1.10.0", "2.0.9", "2.1.0"].