haar_lib/algo/
merge.rs

1//! ソート済み配列のマージ
2
3/// `a[0..k]`と`a[k..]`を`cmp`で比較してマージする。
4pub fn inplace_merge_by<T: Copy>(a: &mut [T], k: usize, cmp: fn(&T, &T) -> bool) {
5    let fst = a[0..k].to_vec();
6    let snd = a[k..].to_vec();
7
8    let mut i = 0;
9    let mut j = 0;
10    let mut k = 0;
11
12    loop {
13        if i >= fst.len() {
14            if j >= snd.len() {
15                break;
16            } else {
17                a[k] = snd[j];
18                j += 1;
19            }
20        } else if j >= snd.len() || cmp(&fst[i], &snd[j]) {
21            a[k] = fst[i];
22            i += 1;
23        } else {
24            a[k] = snd[j];
25            j += 1;
26        }
27        k += 1;
28    }
29}
30
31/// `a[0..k]`と`a[k..]`を`<`で比較してマージする。
32pub fn inplace_merge<T: Ord + Copy>(a: &mut [T], k: usize) {
33    inplace_merge_by(a, k, |x, y| x < y);
34}
35
36/// 2つのソート済み`Vec`をマージした`Vec`を返す。
37pub fn merge<T: Ord + Copy>(mut a: Vec<T>, mut b: Vec<T>) -> Vec<T> {
38    let n = a.len();
39    a.append(&mut b);
40    inplace_merge(&mut a, n);
41    a
42}
haar_lib/algo/merge.rs

haar_lib/algo/
merge.rs
