Rust merge

rust

use std::borrow::BorrowMut;
use std::ptr::replace;

pub fn do_sth() {

  test_merge_sort();
}

fn merge_sort(to_sort: &mut Vec<i32>, all: &mut Vec<i32>) {
    let len = to_sort.len();

    if len <= 1 { return }
    else {
        let mid = len / 2;
        let (l, r) = to_sort.split_at_mut(mid);
        let left = &mut l.to_vec();
        let right = &mut r.to_vec();
        merge_sort(&mut left.to_vec(), all);
        merge_sort(&mut right.to_vec(), all);

        merge(left, right, all);
    }
}

// 把两个已经排序的数组，合并成一个排序的数组
fn merge(left: &mut Vec<i32>, right: &mut Vec<i32>, all: &mut Vec<i32>) {
    // 对比两个数组，如果有一个是空，附加上非空的数组
    // 如果两个数组都非空，比较第一个元素，把第一个元素附加到all上

    match (left.first(), right.first()) {
        (Some(lh), Some(rh)) => {
            if lh < rh {
                all.push(*lh);
                unsafe { replace(left, left.split_first().unwrap().1.to_vec()); }
            } else {
                all.push(*rh);
                unsafe { replace(right, right.split_first().unwrap().1.to_vec()); }
            }
        },
        (None, Some(rh)) => {
            all.push(*rh);
            unsafe { replace(right, right.split_first().unwrap().1.to_vec()); }
        },
        (Some(lh), None) => {
            all.push(*lh);
            unsafe { replace(left, left.split_first().unwrap().1.to_vec()); }
        },
        _ => return
    }

    merge(left, right, all);
}

fn test_merge() {
    let (mut l, mut r) = (vec![1, 2, 5, 6], vec![4, 7, 8, 10]);
    let mut all = vec![];
    merge(&mut l, &mut r, &mut all);
    println!("{:?} {:?} {:?}", l, r, all);
}

fn test_merge_sort() {
    let mut origin = vec![1, 3, 2, 8, 9, 4, 7, 6, 5, 0];
    let mut all = vec![];
    merge_sort(&mut origin, &mut all);
    
    assert_eq!(all, vec![0, 1, 2, 3, 4, 5, 6, 7, 8, 9]);
    //println!("{:?} {:?}", origin, all);
}

/// 使用归并排序数组
fn merge_sort(to_sort: &mut Vec) -> Vec {
let len = to_sort.len();

if len <= 1 { return to_sort.to_owned() }
else {
    let mid = len / 2;
    let (l, r) = to_sort.split_at_mut(mid);
    let left = &mut l.to_vec();
    let right = &mut r.to_vec();
    let mut left = merge_sort(&mut left.to_vec());
    let mut right = merge_sort(&mut right.to_vec());

    let mut all = vec![];
    let r = merge(&mut left, &mut right, &mut all);
    r
}

}