Function gallop

publication/code/chapter07/tim_sort.rs:90–136

跳跃式模糊查找，确定位置

(key: &i32, list: &[i32], mode: Mode)

// 跳跃式模糊查找，确定位置
fn gallop(key: &i32, list: &[i32], mode: Mode) -> (usize, usize) {
    let len = list.len();
    if len == 0 {
        return (0, 0);
    }

    match mode {
        Mode::Forward => {
            let mut prev_val = 0;
            let mut next_val = 1;
            while next_val < len {
                if &list[next_val] < key {
                    prev_val = next_val;
                    next_val = 2 * (next_val + 1) - 1;
                } else if &list[next_val] == key {
                    next_val += 1;
                    break;
                } else {
                    break;
                }
            }

            if next_val > len {
                next_val = len;
            }
            (prev_val, next_val - prev_val)
        }
        Mode::Reverse => {
            let mut prev_val = len;
            let mut next_val = (prev_val + 1) / 2 - 1;
            loop {
                if &list[next_val] > key {
                    prev_val = next_val + 1;
                    next_val = (next_val + 1) / 2;
                    if next_val != 0 {
                        next_val -= 1;
                    } else {
                        break;
                    }
                } else {
                    break;
                }
            }
            (next_val, prev_val - next_val)
        }
    }
}

// A、B、C 归并排序
fn merge_sort(list: &mut [i32], mut first_len: usize) {