Rust beginner implementing some sorts

Question

I'm starting to learn Rust. After reading through chapter 13 of the Rust Book, I've gone and implemented a handful of sorting algorithms for practice with the language.

Would love to learn some more experiences Rustacean's tips on ways to make this code more idiomatic. I have some particular difficulties with mergesort -- I am not sure how to making some unnecessary copies without changing the function signature from Vec<u32> to &[u32].

use std::collections::HashMap;

pub fn bubble_sort(vec: &mut Vec<u32>) -> &Vec<u32> {
    if vec.len() == 0 {
        return vec;
    }

    let mut swap_seen = true;
    while swap_seen {
        swap_seen = false;
        for mut i in 0..(vec.len() - 1) {
            while (i < (vec.len() - 1)) && (vec[i] > vec[i + 1]) {
                let (a, b) = (vec[i], vec[i + 1]);
                vec[i + 1] = a;
                vec[i] = b;
                swap_seen = true;
                i += 1;
            }
        }
    }
    vec
}

pub fn selection_sort(vec: &mut Vec<u32>) -> &Vec<u32> {
    if vec.len() == 0 {
        return vec;
    }

    for i in 0..(vec.len()) {
        let mut smallest_idx = i;
        for j in (i + 1)..(vec.len()) {
            if vec[j] < vec[smallest_idx] {
                smallest_idx = j;
            }
        }
        let (a, b) = (vec[i], vec[smallest_idx]);
        vec[i] = b;
        vec[smallest_idx] = a;
    }
    vec
}

pub fn counting_sort(vec: &mut Vec<u32>) -> Vec<u32> {
    if vec.len() == 0 {
        return vec![];
    }

    // The type matters. HashMap implements its methods using traits, and if you don't pick
    // the right types the traits won't apply and the methods won't show up.
    let mut counts: HashMap<&u32, u32> = HashMap::new();

    for val in vec.iter() {
        // Interesting usage note. This doesn't work:
        //
        // match counts.get(val) {
        //     Some(n_val) => counts.insert(val, n_val + 1),
        //     None => counts.insert(val, 1),
        // };
        //
        // Why not?
        // counts.get(val) is an immutable borrow of the counts hashmap.
        // counts.insert(val) is a mutable borrow of the counts hashmap.
        // This violates the constraint that only one mutable or any number of immutable
        // borrows may be live at a time. However, it only throws a warning, not an error, for
        // some reason. Ref:
        // https://discord.com/channels/442252698964721669/448238009733742612/763950019681583152
        //
        // That brings us to this working code. The "entry API" is specifically designed to avoid
        // this problem. In general, many APIs in Rust are designed around such concerns.
        *counts.entry(val).or_default() += 1;
    }

    let mut sorted: Vec<u32> = vec![];

    for digit in 0..=9u32 {
        let digit_ref = &digit;
        let digit_count = counts.get(digit_ref);

        match digit_count {
            Some(count) => {
                for _ in 0..(*count as i32) {
                    sorted.push(digit);
                }
            },
            None => (),
        }
    }

    sorted
}

pub fn insertion_sort(vec: &mut Vec<u32>) -> &Vec<u32> {
    // usize is Rust's "architecture-dependent integer size". It is u32 on 32-bit systems and
    // u64 on 64-bit systems. usize is used in certain places in Rust lang where this low-level
    // detail matters, e.g. if indexing into memory. It's used to represent array sizes I guess
    // because array length maximum is the architecture's word size.
    for i in 0..(vec.len()) {
        for j in 0..i {
            if vec[j] > vec[i] {
                let (a, b) = (vec[i], vec[j]);
                vec[j] = a;
                vec[i] = b;
            }
        }
    }
    vec
}

pub fn quicksort(vec: Vec<u32>) -> Vec<u32> {
    if vec.len() <= 1 {
        return vec;
    }

    let pivot_idx = ((vec.len() as f32) / 2.0).floor() as usize;
    let pivot_val = vec[pivot_idx];
    let mut left: Vec<u32> = Vec::new();
    let mut right: Vec<u32> = Vec::new();
    for val in ([&vec[..pivot_idx], &vec[(pivot_idx + 1)..]].concat()).into_iter() {
        if val < pivot_val {
            left.push(val);
        }
        else {
            right.push(val);
        }
    }

    let mut result = quicksort(left);
    result.push(pivot_val);
    let mut right = quicksort(right);
    result.append(&mut right);
    result
}

pub fn mergesort(vec: Vec<u32>) -> Vec<u32> {
    let join = |left: Vec<u32>, right: Vec<u32>| -> Vec<u32> {
        let (mut j, mut k) = (0, 0);
        let mut result: Vec<u32> = vec![];
        while j < left.len() && k < right.len() {
            if left[j] < right[k] {
                result.push(left[j]);
                j += 1;
            }
            else {
                result.push(right[k]);
                k += 1;
            }
        }
        while j < left.len() {
            result.push(left[j]);
            j += 1;
        }
        while k < right.len() {
            result.push(right[k]);
            k += 1;
        }

        result
    };

    if vec.len() <= 1 {
        return vec;
    }
    // Nit: eliminate this additional base case.
    if vec.len() == 2 {
        if vec[0] < vec[1] {
            return vec;
        } else {
            return vec![vec[1], vec[0]];
        }
    }

    // TODO: how do I eliminate this copy without changing the function signature from Vec<u32>
    // to &[u32]?
    let pivot = (((vec.len() as f32) / 2.0).floor()) as usize;
    let mut left: Vec<u32> = Vec::new();
    left.extend_from_slice(&vec[..pivot]);
    let mut right: Vec<u32> = Vec::new();
    right.extend_from_slice(&vec[pivot..]);

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

    join(left, right)
}
```

Answer 1

On the whole, your Rust code looks good to me. You make appropriate use of the standard library and language features like closures. Nothing stands out as especially unidiomatic; even the formatting looks nice.

That said, of course there are always things that could be improved.

General observations

• If you're not using rustfmt yet, start now. Your formatting is basically identical to the rustfmt defaults, but an automated formatting tool has the advantage of finding the occasional mistake as well as making code look pretty.
• Except for counting_sort and mergesort, these algorithms are all in-place and work on slices, so they should accept &mut [u32] instead of &mut Vec<u32>. This makes it possible to sort arrays and other array-like data structures as well as Vectors.
• Returning &Vec<u32> from the sort function allows it to be used like foo(sort(&mut xs)) (foo will receive the sorted array). However, this can be misleading because the sort function actually mutates xs, which can be easily overlooked if it occurs in the middle of a more complicated expression. It's better for functions that mutate their arguments not to also return them, so the calling code is more obvious (sort(&mut xs); foo(&xs)). The standard library sort functions do not return anything.
• Use the slice swap method to swap two elements by index (not to be confused with the std::mem::swap function, which swaps the contents of any two &mut references).
• With the exception of counting_sort, all of these functions order the elements by comparing them, so they ought to work just as well with slices of any type that can be compared with Ord¹ -- not just u32. There's nothing wrong with writing a function that only sorts u32s, and in some cases that may even be desirable (for type inference, for example); however, it's nearly as easy to be generic as not, and even if you never expect to use the function with more than one type, coding to an interface (T: Ord) can help you avoid bugs that result from over-focusing on a particular implementation (u32).
• There is an .is_empty() function on slices you can use in place of .len() == 0.
• Note that .. and ..= have the lowest precedence of any operator except the assignment operators. So you don't need to parenthesize, unless you find it helpful for readability.
• Don't write for r in vec.iter() or for v in vec.into_iter(). The for loop calls into_iter() implicitly. Use for r in &vec and for v in vec instead.

Bubble sort

coyotte508's answer already suggested a fix for this, but the nested loop does some unnecessary comparisons because i does not increase monotonically. You probably expected that after the while loop was finished, the for loop would pick up where it left off with the current value of i, but for loops don't work like that in Rust.

bubble_sort also does extra work when the end of the array is already sorted. During a bubble sort, there's a section of the array that's already sorted, and each iteration of the outer loop grows that section by at least 1 (but sometimes more). You can exploit this fact by keeping track of the index of the last swap performed. At the end of each iteration of the outer loop, the index of the last value swapped is the beginning of the sorted portion of the array, which never needs to be sorted again - so you can use that index instead of vec.len() as a bound for the inner loop, and exit the outer loop when the length of the "unsorted" portion drops to 1 (since an array of length 1 is sorted already). As a bonus, if you initialize it with the length of the slice, you can avoid the initial check against 0.

Finally, it's a minor thing, but you can reduce the number of + 1s and - 1s by iterating from 1 instead of 0.

With all these things in mind, here's how you might write bubble_sort:

pub fn bubble_sort<T: Ord>(vec: &mut [T]) {
    let mut unsorted_len = vec.len();
    while unsorted_len > 1 {
        let mut last_swap = 0;
        for i in 1..unsorted_len {
            if vec[i - 1] > vec[i] {
                vec.swap(i - 1, i);
                last_swap = i;
            }
        }
        unsorted_len = last_swap;
    }
}

Selection sort

This one is pretty textbook. IMO there's not much to improve beyond the general stuff I mentioned earlier, and that the if vec.len() == 0 at the beginning is unnecessary because the for loop will immediately check it again.

pub fn selection_sort<T: Ord>(vec: &mut [T]) {
    for i in 0..vec.len() {
        let mut smallest_idx = i;
        for j in (i + 1)..vec.len() {
            if vec[j] < vec[smallest_idx] {
                smallest_idx = j;
            }
        }
        vec.swap(i, smallest_idx);
    }
}

Insertion sort

Again, pretty textbook. You can start the outer loop at 1 because there's never anything to do at i = 0.

pub fn insertion_sort<T: Ord>(vec: &mut [T]) {
    for i in 1..vec.len() {
        for j in 0..i {
            if vec[j] > vec[i] {
                vec.swap(j, i);
            }
        }
    }
}

Counting sort

This one can't be made generic, and it can't easily be made in-place. However, since it only has to work on integer keys with a limited range, there are some other ways it could be improved.

First, since it isn't in-place, it doesn't need to mutate its input; we can make it accept &[u32]. (It's actually even more general than that: it can sort any sequence of integer values, even ones that are too large to fit in memory at once! But for the moment let's stick with &[u32].)

Next about the HashMap: this is an odd choice for a counting sort because choosing a HashMap<&u32, u32> over a Vec<u32> or even just a plain [u32; 10] (indexed by *val) suggests you're concerned about wasting space for a bunch of empty count-buckets. But usually you use a counting sort because you expect n (size of the input) to be much larger than k (number of buckets), which would only coincide with there being a lot of empty buckets if the data is concentrated into much fewer than k buckets. Probably 98% of the time you're writing a counting sort, you want either an array of buckets or a Vec of buckets. But let's suppose we're in the 2%. We can still replace the HashMap with a BTreeMap, which is more compact, likely faster,² and naturally keeps the keys in order. We'll also copy the key instead of taking a reference to it, since it's a small integer.

Using BTreeMap also lets us sidestep one of the annoying problems of counting sorts: what happens if one of the inputs is out of range? You could solve this problem by asserting the values are always in range, or by restricting the input type to one that only allows the values 0..=9, but that's not always convenient. With BTreeMap the output is always correct. In the worst case scenario, with totally arbitrary inputs, the algorithm degrades to (a poorly-optimized) tree sort, which is still O(n log n).

Checking whether the input is empty at the beginning of the function probably does nothing useful. The function still does the same thing without it, so the best you can hope for is it saves you a handful of instructions (BTreeMap::new does not allocate), at the expense of adding an unavoidable branch at the beginning of every call. I wouldn't put it in unless profiling showed a non-negligible effect.

To help myself not lose track of which u32s are data and which are counts, I'm going to add a type alias Count.

Finally, this loop in the original offers a chance to use some iterator magic:

                for _ in 0..(*count as i32) {
                    sorted.push(digit);
                }

This is not just a tedious piece of boilerplate, but it may also be slow because push might have to reallocate the Vec several times. You could call reserve_exact beforehand, but instead let's replace the whole thing with sorted.extend(std::iter::repeat(digit).take(count)), which can be read almost like English: "extend sorted with repeated copies of digit up to count times".

After making all those changes, here's what I came up with:

pub fn counting_sort(vec: &[u32]) -> Vec<u32> {
    type Count = u32;
    
    let mut counts: BTreeMap<_, Count> = BTreeMap::new();
    for val in vec {
        *counts.entry(*val).or_default() += 1;
    }

    let mut sorted: Vec<Count> = vec![];
    for (digit, count) in counts {
        sorted.extend(std::iter::repeat(digit).take(count as _));
    }
    sorted
}

Quicksort

Okay, I went a little overboard with critiquing counting sort, so I won't do a full rewrite of quicksort. Here's what I noticed.

((vec.len() as f32) / 2.0).floor() as usize is something you should never write. In the first place, truncating vec.len() to f32 loses a lot of precision. This will not give the correct result for large slices. It doesn't really matter to the correctness of the algorithm in this case, but it's a thing to be aware of in general, and it can affect performance. Secondly, floating-point operations are usually significantly slower than comparable integer operations. For both these reasons you should always do integer math with integers. usize division always rounds towards zero, so the whole expression should just be vec.len() / 2.

Also, left and right don't need explicit types; they can be inferred.

Mergesort

Largely already covered by coyotte508.

Further exercises for the reader

• Implement counting_sort using an array instead of a BTreeMap

• Implement counting_sort with this signature:

  fn counting_sort(impl IntoIterator<Item = u32>) -> impl Iterator<Item = u32>;
  

• Implement quicksort using an in-place algorithm.

• Implement heapsort.

---

¹ Why Ord and not PartialOrd? Technically PartialOrd will also compile, but all textbook sorting algorithms assume that the items are comparable -- that is, each item is either greater than, less than, or equal to each other item. Values that are incomparable to other values, as PartialOrd allows, tend to wreak havoc in sorting algorithms.

² The performance analysis is non-trivial. A B-tree is often faster than a hashtable when (1) comparing the keys is much cheaper than hashing them and (2) the keys are needed in order. Both are true here. However, caching also plays a large role and could sway the result, especially if you compare against a fast hasher such as FNV. If you look at only the asymptotic performance, HashMap wins (O(n + k) vs. O((n + k)log(k))), but I'm not convinced there's any value of n and k for which HashMap actually makes the most sense. Frankly, I also just wanted to write it with BTreeMap to make it more concise. If you were writing this code in a "real world" programming scenario, you'd want to profile it rather than just guessing.

Answer 2

This answer is only about mergesort

I don't see why you don't want mergesort to take &[u32] as an argument - it makes the function more generic! I read in the rust book that rustaceans prefer to use &str instead of &String as an argument for that reason ;)

I'm new to Rust as well - sorry! - and decided to try my hand at this.

Edge cases

My first comment is not rust-specific (all the others are) this:

    if vec.len() <= 1 {
        return vec;
    }
    // Nit: eliminate this additional base case.
    if vec.len() == 2 {
        if vec[0] < vec[1] {
            return vec;
        } else {
            return vec![vec[1], vec[0]];
        }
    }

It can be rewritten like this:

    if vec.len() == 2 && vec[0] > vec[1] {
        return vec![vec[1], vec[0]];
    }
    if vec.len() <= 2 {
        return vec;
    }

pivot

    let pivot = (((vec.len() as f32) / 2.0).floor()) as usize;

When dividing a positive int by another positive int, the result is the same as in C / C++: you don't get what's after the floating point. You can just do:

    let pivot = vec.len() / 2;

Signature change

Let's study the signature of your function - and change it:

pub fn mergesort(vec: Vec<u32>) -> Vec<u32>;

It takes a Vec<u32> - not as a reference, so it moves the data into the function. The argument becomes unusable by the caller of the function. It then returns a new Vec<u32>.

For example, this code won't work, since vec was moved, it can't be used in the println!:

fn main() {
  let vec = vec![2,1,0,4,5];
  let sorted = mergesort(vec);

  println!("Original: {:?}, sorted: {?:}", vec, sorted);
}

Given that, there is no downside to use &mut [u32] as the type, and reorder in place:

pub fn mergesort(vec: &mut [u32]);

Now mergesort borrows a mutable slice.

Now you probably have plenty of errors :)

Let's look at the last part:

    let mut left: Vec<u32> = Vec::new();
    left.extend_from_slice(&vec[..pivot]);
    let mut right: Vec<u32> = Vec::new();
    right.extend_from_slice(&vec[pivot..]);

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

    join(left, right)

Since mergesort takes a mutable reference, it can change to:

    mergesort(&mut vec[..pivot]);
    mergesort(&mut vec[pivot..]);

    join(???)

join function

So now we must change the signature of join, to take two slices as parameters. Actually, I'd like to do this, and have join rewrite the slices in place:

   join (&mut vec[..pivot], &mut vec[pivot..]);

But it's not possible to borrow two mutable references at the same time!

The next best thing, to me, is:

• join borrows two immutable references and returns a Vec
• Then assign the content of the Vec to the slice

So here's the signature:

    let join = |left: &[u32], right: &[u32]| -> Vec<u32> {
        // ...
    };

    let pivot = vec.len() / 2;

    mergesort(&mut vec[..pivot]);
    mergesort(&mut vec[pivot..]);

    let result = join(&vec[..pivot], &vec[pivot..]);
    vec.copy_from_slice(&result[..])

Now we just have to change join ;)

First this:

        while j < left.len() {
            result.push(left[j]);
            j += 1;
        }
        while k < right.len() {
            result.push(right[k]);
            k += 1;
        }

It can be changed to:

        result.extend_from_slice(&left[j..]);
        result.extend_from_slice(&right[k..]);

Now this:

        let (mut j, mut k) = (0, 0);
        let mut result: Vec<u32> = vec![];
        while j < left.len() && k < right.len() {
            if left[j] < right[k] {
                result.push(left[j]);
                j += 1;
            }
            else {
                result.push(right[k]);
                k += 1;
            }
        }

I don't think increasing indexes is in rust philosophy, I'd rather like to use iterators:

        let mut left = left.iter();
        let mut right = right.iter();
        while let (Some(left), Some(right)) = (left.next(), right.next()) {
           // ...
        }

Unfortunately this is not possible, because we only want to advance one side at a time. Well, there is a peekable function for iterators, to check the next value without calling next, which gives this instead for join:

    let join = |left: &[u32], right: &[u32]| -> Vec<u32> {
        let mut result: Vec<u32> = vec![];

        let mut left = left.iter().peekable();
        let mut right = right.iter().peekable();

        while let (Some(left_val), Some(right_val)) = (left.peek(), right.peek()) {
            if left_val < right_val {
                result.push(**left_val);
                left.next(); // only advance left
            } else {
                result.push(**right_val);
                right.next(); // only advance right
            }
        }

        result.extend(left);
        result.extend(right);

        result
    };

I'm not sure if making an iterator peekable is all that great, however. But now you could even change the signature of join to take two mutable Iter as parameters!

Here's another version with just slices:

    let join = |mut left: &[u32], mut right: &[u32]| -> Vec<u32> {
        let mut result: Vec<u32> = vec![];
        
        while left.len() > 0 && right.len() > 0 {
            if left[0] < right[0] {
                result.push(left[0]);
                left = &left[1..];
            } else {
                result.push(right[0]);
                right = &right[1..];
            }
        }
        result.extend_from_slice(&left);
        result.extend_from_slice(&right);

        result
    };

Note that I made the arguments mutable, I could have done this instead:

    let join = |left: &[u32], right: &[u32]| -> Vec<u32> {
        let mut left = left;
        let mut right = right;

        // ...
    };

Final version

pub fn mergesort(vec: &mut [u32]) {
    if vec.len() == 2 && vec[0] > vec[1] {
        vec.swap(0, 1);
    }
    if vec.len() <= 2 {
        return;
    }

    let join = |mut left: &[u32], mut right: &[u32]| -> Vec<u32> {
        let mut result: Vec<u32> = vec![];

        while left.len() > 0 && right.len() > 0 {
            if left[0] < right[0] {
                result.push(left[0]);
                left = &left[1..];
            } else {
                result.push(right[0]);
                right = &right[1..];
            }
        }
        result.extend_from_slice(&left);
        result.extend_from_slice(&right);

        result
    };

    let pivot = vec.len() / 2;

    mergesort(&mut vec[..pivot]);
    mergesort(&mut vec[pivot..]);

    let result = join(&vec[..pivot], &vec[pivot..]);
    vec.copy_from_slice(&result[..])
}

It's easy to get back the original signature as well, if you really want:

pub fn mergesort (vec: Vec<u32>) -> Vec<u32> {
    mergesort_private(&mut vec[..]);
    vec
}

// Original mergesort function, renamed to mergesort_private
fn mergesort_private(vec: &mut [u32]) {
    // ...
}

Bonus: bubble_sort

Without changing the signature of the function (& mut[u32] could be used), here it is transformed:

pub fn bubble_sort(vec: &mut Vec<u32>) -> &Vec<u32> {
    loop {
        let mut swap_seen = false;

        for i in 0..(vec.len() - 1) {
            if vec[i] > vec[i + 1] {
                vec.swap(i, i + 1);
                swap_seen = true;
            }
        }

        if !swap_seen {
            break;
        }
    }
    vec
}