# Create merge sort in rust

I am having trouble creating a merge sort algorithm in rust here is what I got so far:

https://play.rust-lang.org/?gist=a87619dc59725e1523c5975aab1bdd8b&version=stable&mode=debug&edition=2015

I am not getting sorted numbers, anyone have a clue what going on?

Vec::pop() pops from the end of the array not the front.

1 Like

This isnâ€™t important, butâ€¦

``````                let temp = a[i];
a[i] = a[i + 1];
a[i + 1] = temp;
``````

Reminder that you can just use `a.swap(i, i+1)` for that: https://doc.rust-lang.org/std/vec/struct.Vec.html#method.swap

4 Likes

thanks I did not think of that

``````pub fn insert_sort(a: &mut Vec<f64>) {
let mut swap = true;
while swap {
swap = false;
for i in 0..a.len()-1 {
if a[i] > a[i+1] {
swap = true;
a.swap(i , i+1);
}
}
}
}
pub fn merge_sort(a: &mut Vec<f64>, b: usize, e: usize) {
if b < e {
let m = (b+e)/2;
merge_sort(a, b, m);
merge_sort(a, m+1, e);
merge(a, b, m, e);
}
}
fn merge(a: &mut Vec<f64>, b: usize, m:usize, e:usize) {
let mut left = a[b..m+1].to_vec();
let mut right = a[m+1..e+1].to_vec();
left.reverse();
right.reverse();
println!("size of right: {}", right.len());
for k in b..e + 1 {
if left.is_empty() {
a[k] = right.pop().unwrap();
continue;
}
if right.is_empty() {
a[k] = left.pop().unwrap();
continue;
}
if right.last() < left.last() {
a[k] = right.pop().unwrap();
}
else {
a[k] = left.pop().unwrap();
}
}
}
``````

It works!, thanks!

1 Like

I wrote a performance test ( https://github.com/hg2ecz/OptimalSortAlgorythm/ )
â€“> Rust-sort_algorythms (recursive and nonrecursive)
â€“> Rust-sort_algorythms-with-C
Elapsed times:

• Recursive Rust: 233 msec
• nonrecursive Rust: 192 msec
• Rust, but sort in C: 123 msec

Can I improve the speed of nonrecursive Rust code?

The Rust versions of the algorithms do dynamic allocation in every iteration / recursive call while the C versions do not.
For the iterative version you should create the vector `o2` outside of the `while` loop with an initial capacity that matches `o1`. Then you just swap `o1` and `o2` after every iteration.

2 Likes

this reversing seems inefficient; instead of `reverse()` and `pop()`, i think you could use an iterator from both vectors and use `.next()`

you'll not have look-ahead so will need to store a reference to the last element (or None) from both sides

Thank you, the vector o2 is now outside of the while loop, and I swapped o1 and o2
The result is now 148 msec, itâ€™s good.

Yeah it looks like reverse() is in O(n)

yes looks like `slice::reverse()` is linear time as it reverses the elements in-place in memory; there's `Iterator::rev()` which should not have this problemâ€”only changes the iteration directionâ€”but that's not helpful in this specific case as the code needs to iterate in-order, the `reverse()` is there wholly to accommodate `pop()`

TIL thereâ€™s `iterator.peekable`, with which you can straightforwardly rewrite this code as

``````fn merge(a: &mut Vec<f64>, b: usize, m:usize, e:usize) {
let left_vec = a[b..m+1].to_vec();
let mut left = left_vec.iter().peekable();
let right_vec = a[m+1..e+1].to_vec();
let mut right = right_vec.iter().peekable();
for k in b..e + 1 {
if left.peek().is_none() {
a[k] = *right.next().unwrap();
continue;
}
if right.peek().is_none() {
a[k] = *left.next().unwrap();
continue;
}
if right.peek().unwrap() < left.peek().unwrap() {
a[k] = *right.next().unwrap();
}
else {
a[k] = *left.next().unwrap();
}
}
}
``````
2 Likes

One or two things:

• instead of `a..b+1` use `a..=b` (inclusive range)
• iterating over the length of a vec and use `k` as an indexer is not very rusty, instead do something like `for elem in a.iter_mut().take(e + 1).skip(b) {` which uses the Iterator capability of `Vec` (I Iterator!).

If you write code, run clippy to ensure, that your code is rusty enough

3 Likes

thanks for the suggestions, in this specific case this is not possible because `k` is used as write index into the target slice; could do something with `.enumerate` but i donâ€™t think that makes it clearer

1 Like

it is my implementation!

``````// left, right: 0-index of v
fn merge_sort(v: &mut Vec<i32>, left: usize, right: usize) {
if right > left {
let mid = (left + right)/2;
merge_sort(v, left, mid);
merge_sort(v, mid+1, right);
merge(v, left, mid, right);
}
}

fn merge(v: &mut Vec<i32>, left: usize, mid:usize, right:usize) {
let left_vec = v[left..=mid].to_vec();
let right_vec = v[mid+1..=right].to_vec();

let mut left_itr = left_vec.iter().peekable();
let mut right_itr = right_vec.iter().peekable();

for i in left..=right {
match (left_itr.peek(), right_itr.peek()) {
(None, Some(_)) => v[i] = *right_itr.next().unwrap(),
(Some(_), None) => v[i] = *left_itr.next().unwrap(),
(Some(l), Some(r)) if l < r => v[i] = *left_itr.next().unwrap(),
(Some(l), Some(r)) if r < l => v[i] = *right_itr.next().unwrap(),
(Some(_), Some(_)) => v[i] = *left_itr.next().unwrap(),
_ => break
}
}
}

``````

Please donâ€™t revive an old thread like this.