Merge Sort With Rust

Quick, sort; no not with quicksort, with merge sort

Another algorithm to play with. Moving on in the Algorithms book I mentioned in the last post to section 1.4 we come across the merge sort. Another fun one to play with in Rust and to learn vectors just a little better. So let’s code up a quick merge sort with Rust!

Yes, I’m That Old

My AP computer class back around the mid 1980s was in Pascal. I later learned that Pascal was never meant to be used in production – it was a purely a teaching language – even to the extent it could be taught on paper and never even compiled. How terrible it would be not to see your first programs run!

Either way, we worked on terminals and Pascal worked out just fine for me. That language led me easily to C and, though I never used C professionally, that made for an easy transition to Perl (which I have) and to Rust! It turned out, the prior few years of AP tests had been bad enough across all the high schools, they decided to omit three sections of Pascal, unless you optionally wanted to learn them and take an extra AP test, which I did. These three subjects were: recursion (the algorithms both last time and this time use recursion), linked list (that broke my brain for a little while – I was glad later on that it happened in school because it made C so much easier to learn), and sorting (without any simple, built-ins).

Merging with Rust

I am sure I learned the simple merge sort back then, 35 years ago. Heck, that means it was only 40 years old when I learned it! The book only spends a couple of pages on it – it is just another example of a recursive algorithm. It was fun in Rust though, I learned some vector methods I wasn’t aware of like the various forms of split_at and concat. Again I made a couple of very simple tests just to help show it works.

So, here is the code I came up with:

main.rs for merge sort

use std::env;

#[test]
fn check_mergesort() {
    let letters = vec!["s", "a", "m", "p", "l", "e"];
    let shouldbe = vec!["a", "e", "l", "m", "p", "s"];
    let sorted = mergesort(letters);
    assert_eq!(sorted, shouldbe);

    let words = vec![
        "now", "is", "the", "time", "for", "all", "good", "men", "to", "come", "to", "the", "aid",
        "of", "their", "country",
    ];
    let shouldbe = vec![
        "aid", "all", "come", "country", "for", "good", "is", "men", "now", "of", "the", "the",
        "their", "time", "to", "to",
    ];
    let sorted = mergesort(words);
    assert_eq!(sorted, shouldbe);
}

/// Adapted from reading "Algorithms" by Jeff Erickson
/// freely available on http://jeffe.cs.illinois.edu/teaching/algorithms/
pub fn main() {
    let args: Vec<String> = env::args().collect();

    if args.len() < 2 {
        println!(
            "Usage: {} word word [word...] (two or more words to sort)",
            args[0]
        );
        return;
    }

    let words = args.iter().skip(1).map(AsRef::as_ref).collect();
    println!("Arrived: {:?}", words);

    let sorted = mergesort(words);
    println!("Sorted: {:?}", sorted);
}

/// Mergesort
/// Section 1.4, page 27
pub fn mergesort(words: Vec<&str>) -> Vec<&str> {
    if words.len() < 2 {
        return words;
    }

    let midpoint = (words.len() + 1) / 2;
    let (left, right) = words.split_at(midpoint);

    let left = mergesort(left.to_vec());
    let right = mergesort(right.to_vec());

    let halfsort = [left, right].concat();
    let sorted = merge(halfsort, midpoint);

    return sorted;
}

pub fn merge(words: Vec<&str>, midpoint: usize) -> Vec<&str> {
    let size = words.len();
    let mut left_index = 0;
    let mut right_index = midpoint;
    let mut sorted: Vec<&str> = Vec::new();

    for _ in 0..size {
        if right_index >= size {
            sorted.push(&words[left_index]);
            left_index += 1;
        } else if left_index >= midpoint {
            sorted.push(&words[right_index]);
            right_index += 1;
        } else if words[left_index] < words[right_index] {
            sorted.push(&words[left_index]);
            left_index += 1;
        } else {
            sorted.push(&words[right_index]);
            right_index += 1;
        }
    }
    return sorted;
}

There is not really much to say about it though – unless you have questions or suggestions. Check it out in the github repo.

The post Merge Sort With Rust appeared first on Learning Rust.