マージソートのプログラム
RUST の（自分のための）チュートリアル的な観点から基本的な記法の説明も書く。

いつものマージソート。

マージソートのエントリーポイント。

fn merge_sort<T: Copy + Ord>(arr: &mut [T]){
    if arr.len() < 2{
        return ;
    }
    let mid = arr.len() / 2;
    let mut tmp = arr.to_vec() ;

    merge_sort(&mut arr[..mid]);
    merge_sort(&mut arr[mid..]);

    merge(&arr[..mid], &arr[mid..], &mut tmp);

    arr.copy_from_slice(&tmp);
}

マージソートの雑な説明

1. 要素が1つになるまで配列を2分割していく
2. 分割された2つの配列を先頭から見て、整列しながら併合（マージ）する

fn merge_sort<T: Copy + Ord>(arr: &mut [T])

まず、マージソートの関数定義。
ジェネリックデータ型を使って、Copy 可能な全順序集合（Ord）に対してソートを実行できるように宣言。
複数のトレイト境界は、このように “+” を使って指定することができる。
Copy を指定しないと arr.to_vec や、 arr.copy_from_slice が使えないぞ。（arr.to_vec は Clone トレイトで十分だが、arr.copy_from_slice は Copy トレイトが必要）

let mut tmp = arr.to_vec() ;

分割した2つの配列から、1つのソートされた配列を作成するために一時的に使用する配列を定義している。もちろん可変。
元の配列 arr を新しい Vec に clone する。これは、 arr と同じ長さの Vec を生成したいから。
let mut tmp = Vec::new(); みたいな感じにして Vec を作ると、merge 関数の中で index out of bounds するぞ。
新しい Vec を使ってみてもできる実装はあるんだろうな～

merge_sort(&mut arr[..mid]); merge_sort(&mut arr[mid..]);

可変スライスを使って配列の一部を参照する。
スライスを使わずに、配列全体の参照と添え字を（そのような関数を定義すれば）関数に渡すこともできるが、スライスを使って必要な分を渡すようにすればスマート。しかも後で便利。

merge(&arr[..mid], &arr[mid..], &mut tmp);

ソートされた配列を2つ渡して1つの配列にしてもらう。
tmp にソート済み配列が格納される。

arr.copy_from_slice(&tmp);

arr にソート済みの配列 tmp をコピーする。
可変スライスを使っていたから arr に tmp をコピーしてしまうだけで必要なところだけを書き換えることができる。

マージする部分

fn merge<T: Copy + Ord>(left: &[T], right: &[T], tmp: &mut [T]){
    let mut l = 0;
    let mut r = 0;
    let mut i = 0;

    while l < left.len() && r < right.len(){
        if left[l] <= right[r]{
            tmp[i] = left[l];
            i += 1;
            l += 1;
        }else{
            tmp[i] = right[r];
            i += 1;
            r += 1;
        }
    }

    if l < left.len() {
        tmp[i..].copy_from_slice(&left[l..]);
    }

    if r < right.len() {
        tmp[i..].copy_from_slice(&right[r..]);
    }

}

2つのソート済み配列をマージして1つの配列にする。
それぞれの配列の先頭を見て、小さい方を tmp に入れていく。
どっちかの配列の要素をすべて tmp に入れ終わったら、残った配列の要素はまとめて全部 tmp の後ろにコピーする。

全体のソースコード

fn main() {
    let mut arr = [2,4,1,3,10,8,5,4];

    merge_sort(&mut arr);

    println!("ans = {:?}",arr);
}

fn merge_sort<T: Copy + Ord>(arr: &mut [T]){
    if arr.len() < 2{
        return ;
    }
    let mid = arr.len() / 2;
    let mut tmp = arr.to_vec() ;

    merge_sort(&mut arr[..mid]);
    merge_sort(&mut arr[mid..]);

    merge(&arr[..mid], &arr[mid..], &mut tmp);

    arr.copy_from_slice(&tmp);
}

fn merge<T: Copy + Ord>(left: &[T], right: &[T], tmp: &mut [T]){
    let mut l = 0;
    let mut r = 0;
    let mut i = 0;

    while l < left.len() && r < right.len(){
        if left[l] <= right[r]{
            tmp[i] = left[l];
            i += 1;
            l += 1;
        }else{
            tmp[i] = right[r];
            i += 1;
            r += 1;
        }
    }

    if l < left.len() {
        tmp[i..].copy_from_slice(&left[l..]);
    }

    if r < right.len() {
        tmp[i..].copy_from_slice(&right[r..]);
    }

}