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]) { // ... }