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

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

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

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.