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 :heart: Iterator!).

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

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.