Rustでマージソートを実装するのが大変だった

# 背景

`Rust`練習のために、とりあえずWikipediaに載っているソートアルゴリズム全部実装する！→マージソートは所有権的に実装難しそう？とりあえずやってみよう

# 結論

`Vec`のソートアルゴリズムはマージソート(と要素数の少ないときはインサートソート)なので、使えるなら使おう

```rust
vec![2, 0, 1].sort();
```

[Rustドキュメント](https://doc.rust-lang.org/std/primitive.slice.html#current-implementation-6)
> The current algorithm is an adaptive, iterative merge sort inspired by timsort.

訳：現在のアルゴリズムは`Timsort`に触発された適応的で反復型のマージソートです。

[Rustソースコード](https://github.com/rust-lang/rust/blob/master/library/alloc/src/slice.rs#L268)

# とは言うものの...

やっぱり実装したい！
ので、所有権システムのために3つの選択肢を考えた。

1. `Copy`トレイトを強制
1. `Default`トレイトを強制
1. `unsafe`を使う

まず、マージソートは、

1. 左半分をソート
1. 右半分をソート
1. 左右のソート結果を合成
 
という手順のアルゴリズム。
`Python`で大まかな実装を示す。

```py
import copy

def merge_sort(array):
    if len(array) <= 1:
        return array

    middle = len(array) // 2
    left = merge_sort(array[:middle])
    right = merge_sort(array[middle:])

    # 右のソート済み配列を逆順にして結合
    merge = copy.copy(left + right[::-1])
    l = 0
    r = len(array) - 1
    for i in range(len(array)):
        if merge[l] > merge[r]:
            array[i] = merge[r]
            r -= 1
        else:
            array[i] = merge[l]
            l += 1
    return array
```

この時、鬼門になるのは
`copy.copy(left + right[::-1])`
の部分だ。

スライスに「スライスに格納されている値」の所有権があるため、気軽に値を移動させることができない。

## 1.Copyトレイトを使う

回答はシンプルで、Copyできるように(`Copy`トレイトの実装を要求)すれば万事解決がその1。

```rust
fn merge_sort<T: Ord + Copy>(data: &mut [T]) {
    if data.len() <= 1 {
        return;
    }

    let length = data.len();
    let middle = length / 2;
    merge_sort(&mut data[..middle]);
    merge_sort(&mut data[middle..]);

    let mut work_vec: Vec<T> = Vec::with_capacity(length);
    for i in 0..length {
        work_vec.push(data[i]);
    }

    work_vec[middle..].reverse();

    let mut l = 0;
    let mut r = length - 1;

    for i in 0..length {
        if work_vec[l] > work_vec[r] {
            data[i] = work_vec[r];
            r -= 1;
        } else {
            data[i] = work_vec[l];
            l += 1;
        }
    }
}
```

## 2. Defaultトレイトを使う

`std::mem::take`を使って所有権を奪う。これが一番好き。`Default`トレイトは実装していることが多いし。`Default`の実装次第では遅いかも。

```rust
fn merge_sort<T: Ord + Default>(data: &mut [T]) {
    if data.len() <= 1 {
        return;
    }

    let length = data.len();
    let middle = length / 2;
    merge_sort(&mut data[..middle]);
    merge_sort(&mut data[middle..]);

    let mut work_vec: Vec<T> = Vec::with_capacity(length);
    for i in 0..length {
        work_vec.push(std::mem::take(&mut data[i]));
    }

    work_vec[middle..].reverse();

    let mut l = 0;
    let mut r = length - 1;

    for i in 0..length {
        if work_vec[l] > work_vec[r] {
            data[i] = std::mem::take(&mut work_vec[r]);
            r -= 1;
        } else {
            data[i] = std::mem::take(&mut work_vec[l]);
            l += 1;
        }
    }
}
```

## 3. unsafeを使う

正直自信ない...
Rust公式は`unsafe`を使った実装だった。
`copy_to_nonoverlapping`を使い、スライスを全てコピーする。
もっとドキュメント読み込んで自信が持てたらこれがベストだと思う。バグあったらすいません

**2021/6/25 修正しました**

### 2021/6/25追記

@vain0x さんからの指摘で、コードが未定義動作を引き起こす問題がありました。
問題を修正するまでコードを削除しておきます。

### 2021/6/25追記

あまり美しくないが、暫定修正版を出しておく。
値を`copy_to_nonoverlapping()`でコピーし、その後`work_vec`の長さを0にすることで`work_vec`に格納されている値からまだ使われているメモリが解放されることを防ぐ。

```rust
fn merge_sort<T: Ord>(data: &mut [T]) {
    if data.len() <= 1 {
        return;
    }

    let length = data.len();
    let middle = length / 2;
    merge_sort(&mut data[..middle]);
    merge_sort(&mut data[middle..]);

    let mut work_vec: Vec<T> = Vec::with_capacity(length);
    unsafe {
        data.as_ptr()
            .copy_to_nonoverlapping(work_vec.as_mut_ptr(), length);
        work_vec.set_len(length);
    }

    work_vec[middle..].reverse();

    let mut l: isize = 0;
    let mut r: isize = length as isize - 1;
    for i in 0..length {
        if work_vec[l as usize] > work_vec[r as usize] {
            unsafe {
                work_vec
                    .as_ptr()
                    .offset(r)
                    .copy_to_nonoverlapping(data.as_mut_ptr().offset(i as isize), 1);
            }
            r -= 1;
        } else {
            unsafe {
                work_vec
                    .as_ptr()
                    .offset(l)
                    .copy_to_nonoverlapping(data.as_mut_ptr().offset(i as isize), 1);
            }
            l += 1;
        }
    }

    unsafe {
        work_vec.set_len(0);
    }
}
```

#### ※絶対に使わないこと　今までのコードとダメな理由

このコードがダメな理由は未定義動作を引き起こすのと、二重メモリ解放を起こすこと。完全にunsafeの反面教師みたいなコードだった。
※パフォーマンスも悪い(`work_vec.remove(0)`によって)が、これは今回は置いておく

**初心者の推論と検証なので鵜呑みにしないでください**

```rust
fn merge_sort<T: Ord>(data: &mut [T]) {
    if data.len() <= 1 {
        return;
    }

    let length = data.len();
    let middle = length / 2;
    MergeSort::merge_sort(&mut data[..middle]);
    MergeSort::merge_sort(&mut data[middle..]);

    let mut work_vec: Vec<T> = Vec::with_capacity(length);
    unsafe {
        data.as_ptr()
            .copy_to_nonoverlapping(work_vec.as_mut_ptr(), length);
        work_vec.set_len(length);
    }

    work_vec[middle..].reverse();

    let mut r = length;

    for i in 0..length {
        r -= 1;
        if work_vec[0] > work_vec[r] {
            data[i] = work_vec.remove(r);
        } else {
            data[i] = work_vec.remove(0);
        }
    }
}
```

このコードで、以下のような型をソートしようとする。

```rust
struct BoxedValue {
    value: Box<i32>,
}

impl Ord for BoxedValue {
    // 省略 実際はPartialOrd、PartialEq, Eqもいる
    // 比較はself.value.deref().cmp(&*other.value)のような形
}
```

まず、`data`から`work_vec`に値がコピーされる。この時のコピーはCの`memcpy`と同じ挙動のため、Shallow Copyになる(Boxの中身はコピーされず、参照がコピーされる)

```rust
data.as_ptr().copy_to_nonoverlapping(work_vec.as_mut_ptr(), length);
```

そして、`work_vec`の保持している値(`data`からコピーしたもの)が`data`に束縛される(所有権の移動)

```rust
data[i] = work_vec.remove(0);
```

このとき、まず`work_vec.remove(0)`が評価され、`work_vec[0]`を初期化(メモリ解放)しようとする(`Box<i32>`を経由して`i32`を初期化(メモリを解放、`free()`を呼び出し)する)。
次に、`data[i]`は既に初期化(メモリ割り当て、値で初期化)済みであることをRustコンパイラは知っているため、これも初期化(メモリ解放)しようとする。
このとき、`work_vec`と`data`の中身は順序は違うものの同一のため、最初の`work_vec.remove()`と、`data[i]`への値束縛時に同じメモリが解放される(計二回)。そして2重メモリ解放の実行時エラーが出る。

参考：[Rustnomicon: チェックされない初期化されていないメモリ](https://doc.rust-jp.rs/rust-nomicon-ja/unchecked-uninit.html)

**初心者の推論と検証なので鵜呑みにしないでください**

# 最後に

ソートならサクサク書けるかな？と思ったけど、全然そんなことはなかった。
今回のでだいぶ勉強になったし、次はそんなに迷わないと信じたい