Method merge_collapse

publication/code/chapter07/tim_sort.rs:577–616

合并 run 使得 A > B + C、B > C 如果 A <= B + C，则 A 和 C 中较小的和 B 合并 如果只有 A、B，则 A <= B 时 A 和 B 合并

(&mut self)

    // 如果 A <= B + C，则 A 和 C 中较小的和 B 合并
    // 如果只有 A、B，则 A <= B 时 A 和 B 合并
    fn merge_collapse(&mut self) {
        let runs = &mut self.runs;
        while runs.len() > 1 {
            let n = runs.len() - 2;

            // 判断 A、B、C、D 的关系，加入 D 是为了防止特殊情况的 Bug
            // A <= B + C || D <= A + B
            if (n >= 1 && runs[n - 1].len <= runs[n].len + runs[n + 1].len)
                || (n >= 2 && runs[n - 2].len <= runs[n].len + runs[n - 1].len)
            {
                // 三个连续的 run: A、B、C，判断其长度关系并进行合并
                // n - 1 对应 A、 n 对应 B、n + 1 对应 C
                let (pos1, pos2) = if runs[n - 1].len < runs[n + 1].len {
                    (n - 1, n) // A B 合并
                } else {
                    (n, n + 1) // B C 合并
                };

                // 取出待合并的 run1 和 run2
                let (run1, run2) = (runs[pos1], runs[pos2]);
                debug_assert_eq!(run1.pos + run1.len, run2.pos);

                // 合并 run1 和 run2 到 run1，其实就是更新 run1 的参数并删除 run2，
                // run1 下标不变，但合并后长度是 run1 和 run2 长度之和
                runs.remove(pos2);
                runs[pos1] = Run {
                    pos: run1.pos,
                    len: run1.len + run2.len,
                };

                // 取出合并后的 run1 去进行归并排序
                let new_list = self.list
                    .split_at_mut(run1.pos).1
                    .split_at_mut(run1.len + run2.len).0;
                merge_sort(new_list, run1.len);
            } else {
                break;
            }
        }
    }

    // 集合处理完了就强制合并剩余的 run 到只剩下一个 run
    fn merge_force_collapse(&mut self) {