Rustでソートアルゴリズム (4)マージソート

## 概要
$O(n\log n)$で完了する安定ソートであるマージソートを実装する。
なお、マージソートにはトップダウン型とボトムアップ型の２つがあるが、両方実装してみる。

具体的なソートの方法については[Wikipedia参照](https://ja.wikipedia.org/wiki/マージソート, "マージソート - Wikipedia")

## 前提条件
[前回](http://qiita.com/chalharu/items/0d1abd098b902a821775)と同様にRustのバージョンは1.19.0とします。

```shell
% rustc --version
rustc 1.19.0 (0ade33941 2017-07-17)
```

## トップダウン型マージソート

```rust:トップダウン型マージソート
fn sort<T: PartialOrd + Clone>(source: &mut [T]) {
    fn sort_inner<TInner: PartialOrd + Clone>(source: &mut [TInner], work: &mut [TInner]) {
        if source.len() > 1 {
            let mid = source.len() >> 1;
            sort_inner(&mut source[..mid], work);
            sort_inner(&mut source[mid..], work);
            work[..mid].clone_from_slice(&source[..mid]);

            let mut left_pos = 0;
            let mut right_pos = mid;
            let mut write_pos = 0;

            loop {
                if work[left_pos] <= source[right_pos] {
                    source[write_pos] = work[left_pos].clone();
                    left_pos += 1;
                    write_pos += 1;
                    if left_pos >= mid {
                        return;
                    }
                } else {
                    source[write_pos] = source[right_pos].clone();
                    right_pos += 1;
                    write_pos += 1;
                    if right_pos >= source.len() {
                        while left_pos < mid {
                            source[write_pos] = work[left_pos].clone();
                            write_pos += 1;
                            left_pos += 1;
                        }
                        return;
                    }
                }
            }
        }
    }

    // 作業メモリ確保
    let mut work = source[..(source.len() >> 1)].to_vec();
    sort_inner(source, &mut work);
}
```

なお、マージソートでは小さな配列に分割していくが、
要素数が少ない場合には挿入ソートの方が速い。

[前々回](http://qiita.com/chalharu/items/3fe582b2fde39f45bf1e)のソースを使用して高速化してみる。


```rust:トップダウン型マージソート+挿入ソート
fn sort<T: PartialOrd + Clone>(source: &mut [T]) {
    const INSERT_THRESHOLD: usize = 32;

    fn insert_sort<TInner: PartialOrd>(source: &mut [TInner]) {
        let ptr = source.as_mut_ptr();
        for i in 1..source.len() {
            let mut j = i;
            unsafe {
                let mut t: TInner = mem::uninitialized();
                ptr::copy_nonoverlapping(ptr.offset(j as isize), &mut t, 1);
                while 0 < j && *(ptr.offset((j - 1) as isize)) > t {
                    ptr::copy_nonoverlapping(
                        ptr.offset((j - 1) as isize),
                        ptr.offset(j as isize),
                        1,
                    );
                    j -= 1;
                }
                ptr::copy_nonoverlapping(&t, ptr.offset(j as isize), 1);
                mem::forget(t);
            }
        }
    }

    fn sort_inner<TInner: PartialOrd + Clone>(source: &mut [TInner], work: &mut [TInner]) {
        if source.len() > INSERT_THRESHOLD {
            let mid = source.len() >> 1;
            sort_inner(&mut source[..mid], work);
            sort_inner(&mut source[mid..], work);
            work[..mid].clone_from_slice(&source[..mid]);

            let mut left_pos = 0;
            let mut right_pos = mid;
            let mut write_pos = 0;

            loop {
                if work[left_pos] <= source[right_pos] {
                    source[write_pos] = work[left_pos].clone();
                    left_pos += 1;
                    write_pos += 1;
                    if left_pos >= mid {
                        return;
                    }
                } else {
                    source[write_pos] = source[right_pos].clone();
                    right_pos += 1;
                    write_pos += 1;
                    if right_pos >= source.len() {
                        while left_pos < mid {
                            source[write_pos] = work[left_pos].clone();
                            write_pos += 1;
                            left_pos += 1;
                        }
                        return;
                    }
                }
            }
        } else {
            // 要素数が少なくなったら挿入ソートに移行
            insert_sort(source);
        }
    }

    let mut work = source[..(source.len() >> 1)].to_vec();
    sort_inner(source, &mut work);
}
```

まぁまぁ早くなったが、要素数によっては[前回](http://qiita.com/chalharu/items/0d1abd098b902a821775)のヒープソートの方がまだ速い。
改善の余地がまだまだあるのだろう。

## ボトムアップ型マージソート

```rust:ボトムアップ型マージソート
fn sort<T: PartialOrd + Clone>(source: &mut [T]) {
    fn sort_inner<TInner: PartialOrd + Clone>(
        work_source: &[TInner],
        work: &mut [TInner],
        size: usize,
    ) {
        let band = size << 1;
        let mut write_pos = 0;
        let b = work_source.len() - size;

        let mut j = 0;
        while j < b {
            let mid = j + size;
            let end = cmp::min(j + band, work_source.len());
            let mut left_pos = j;
            let mut right_pos = mid;

            loop {
                if work_source[left_pos] <= work_source[right_pos] {
                    work[write_pos] = work_source[left_pos].clone();
                    left_pos += 1;
                    write_pos += 1;
                    if left_pos >= mid {
                        while right_pos < end {
                            work[write_pos] = work_source[right_pos].clone();
                            write_pos += 1;
                            right_pos += 1;
                        }
                        break;
                    }
                } else {
                    work[write_pos] = work_source[right_pos].clone();
                    right_pos += 1;
                    write_pos += 1;
                    if right_pos >= end {
                        while left_pos < mid {
                            work[write_pos] = work_source[left_pos].clone();
                            write_pos += 1;
                            left_pos += 1;
                        }
                        break;
                    }
                }
            }
            j += band;
        }

        if j < work_source.len() {
            work[j..work_source.len()].clone_from_slice(&work_source[j..work_source.len()]);
        }
    }

    let mut work = source.to_vec(); // 配列の初期化
    let mut i = 1;
    loop {
        if i < source.len() {
            sort_inner(source, &mut work, i);
            i <<= 1;
        } else {
            return;
        }
        if i < source.len() {
            sort_inner(&work, source, i);
            i <<= 1;
        } else {
            source.clone_from_slice(&work);
            return;
        }
    }
}
```

トップダウン型と比べ、再帰呼び出しがなくなったのが大きなメリットだ。
その為、トップダウン型よりかなり速い。
このコードではメモリ確保量が倍になっているが、メモリ確保量が変わらないコードも書ける。
先程と同様に挿入ソートを利用して高速化してみる。

```rust:ボトムアップ型マージソート+挿入ソート
fn sort<T: PartialOrd + Clone>(source: &mut [T]) {
    const INSERT_THRESHOLD: usize = 32;

    fn partial_insert_sort<TInner: PartialOrd>(source: &mut [TInner], size: usize) {
        let ptr = source.as_mut_ptr();
        let mut left = 0;
        while left < source.len() {
            let right = cmp::min(left + size, source.len());
            for i in left..right {
                let mut j = i;
                unsafe {
                    let mut t: TInner = mem::uninitialized();
                    ptr::copy_nonoverlapping(ptr.offset(j as isize), &mut t, 1);
                    while left < j && *(ptr.offset((j - 1) as isize)) > t {
                        ptr::copy_nonoverlapping(
                            ptr.offset((j - 1) as isize),
                            ptr.offset(j as isize),
                            1,
                        );
                        j -= 1;
                    }
                    ptr::copy_nonoverlapping(&t, ptr.offset(j as isize), 1);
                    mem::forget(t);
                }
            }
            left = right;
        }
    }

    fn sort_inner<TInner: PartialOrd + Clone>(
        work_source: &[TInner],
        work: &mut [TInner],
        size: usize,
    ) {
        let band = size << 1;
        let mut write_pos = 0;
        let b = work_source.len() - size;

        let mut j = 0;
        while j < b {
            let mid = j + size;
            let end = cmp::min(j + band, work_source.len());
            let mut left_pos = j;
            let mut right_pos = mid;

            loop {
                if work_source[left_pos] <= work_source[right_pos] {
                    work[write_pos] = work_source[left_pos].clone();
                    left_pos += 1;
                    write_pos += 1;
                    if left_pos >= mid {
                        while right_pos < end {
                            work[write_pos] = work_source[right_pos].clone();
                            write_pos += 1;
                            right_pos += 1;
                        }
                        break;
                    }
                } else {
                    work[write_pos] = work_source[right_pos].clone();
                    right_pos += 1;
                    write_pos += 1;
                    if right_pos >= end {
                        while left_pos < mid {
                            work[write_pos] = work_source[left_pos].clone();
                            write_pos += 1;
                            left_pos += 1;
                        }
                        break;
                    }
                }
            }
            j += band;
        }

        if j < work_source.len() {
            work[j..work_source.len()].clone_from_slice(&work_source[j..work_source.len()]);
        }
    }

    // 初めにINSERT_THRESHOLDサイズで挿入ソートを行う
    partial_insert_sort(source, INSERT_THRESHOLD);

    if source.len() <= INSERT_THRESHOLD {
        return;
    }

    let mut work = source.to_vec(); // 配列の初期化
    let mut i = INSERT_THRESHOLD;
    loop {
        if i < source.len() {
            sort_inner(source, &mut work, i);
            i <<= 1;
        } else {
            return;
        }
        if i < source.len() {
            sort_inner(&work, source, i);
            i <<= 1;
        } else {
            source.clone_from_slice(&work);
            return;
        }
    }
}
```
やはりこちらも大体においてトップダウン型より速い。
が、なぜか1024要素でソートした場合にはトップダウン型に負けてしまった。

最後に全体的にunsafeを使ってみる。

```rust:ボトムアップ型マージソート+挿入ソート（unsafe）
fn sort<T: PartialOrd>(source: &mut [T]) {
    const INSERT_THRESHOLD: isize = 32;

    fn partial_insert_sort<TInner: PartialOrd>(ptr: *mut TInner, size: isize, len: isize) {
        let mut left = 0;
        while left < len {
            let right = cmp::min(left + size, len);
            for i in left..right {
                let mut j = i;
                unsafe {
                    let mut t: TInner = mem::uninitialized();
                    ptr::copy_nonoverlapping(ptr.offset(j), &mut t, 1);
                    while left < j && *(ptr.offset(j - 1)) > t {
                        ptr::copy_nonoverlapping(ptr.offset(j - 1), ptr.offset(j), 1);
                        j -= 1;
                    }
                    ptr::copy_nonoverlapping(&t, ptr.offset(j), 1);
                    mem::forget(t);
                }
            }
            left = right;
        }
    }

    fn sort_inner<TInner: PartialOrd>(
        ptr: *const TInner,
        wri_ptr: *mut TInner,
        size: isize,
        len: isize,
    ) {
        let band = size << 1;
        let mut write_pos = 0;
        let b = len - size;

        let mut j = 0;
        while j < b {
            let mid = j + size;
            let end = cmp::min(j + band, len);
            let mut left_pos = j;
            let mut right_pos = mid;

            loop {
                unsafe {
                    if *(ptr.offset(left_pos)) <= *(ptr.offset(right_pos)) {
                        ptr::copy_nonoverlapping(
                            ptr.offset(left_pos),
                            wri_ptr.offset(write_pos),
                            1,
                        );
                        left_pos += 1;
                        write_pos += 1;
                        if left_pos >= mid {
                            while right_pos < end {
                                ptr::copy_nonoverlapping(
                                    ptr.offset(right_pos),
                                    wri_ptr.offset(write_pos),
                                    1,
                                );
                                write_pos += 1;
                                right_pos += 1;
                            }
                            break;
                        }
                    } else {
                        ptr::copy_nonoverlapping(
                            ptr.offset(right_pos),
                            wri_ptr.offset(write_pos),
                            1,
                        );
                        right_pos += 1;
                        write_pos += 1;
                        if right_pos >= end {
                            while left_pos < mid {
                                ptr::copy_nonoverlapping(
                                    ptr.offset(left_pos),
                                    wri_ptr.offset(write_pos),
                                    1,
                                );
                                write_pos += 1;
                                left_pos += 1;
                            }
                            break;
                        }
                    }
                }
            }
            j += band;
        }

        if j < len {
            unsafe {
                ptr::copy_nonoverlapping(ptr.offset(j), wri_ptr.offset(j), (len - j) as usize);
            }
        }
    }


    let len = source.len() as isize;
    let src_ptr = source.as_mut_ptr();

    // 初めにINSERT_THRESHOLDサイズで挿入ソートを行う
    partial_insert_sort(src_ptr, INSERT_THRESHOLD, len);

    if len as isize <= INSERT_THRESHOLD {
        return;
    }

    let mut work = Vec::<T>::with_capacity(len as usize); // 配列の初期化
    unsafe {
        work.set_len(len as usize);
    }
    let wrk_ptr = work.as_mut_ptr();
    let mut i = INSERT_THRESHOLD;
    loop {
        if i < len {
            sort_inner(src_ptr, wrk_ptr, i, len);
            i <<= 1;
        } else {
            return;
        }
        if i < len {
            sort_inner(wrk_ptr, src_ptr, i, len);
            i <<= 1;
        } else {
            unsafe {
                ptr::copy_nonoverlapping(wrk_ptr, src_ptr, len as usize);
            }
            return;
        }
    }
}
```

ほぼ同じソースのはずなのにどういうわけか遅くなった。
Clone制約が外れているのがメリットである。