Method merge_force_collapse

publication/code/chapter07/tim_sort.rs:619–650

集合处理完了就强制合并剩余的 run 到只剩下一个 run

(&mut self)

    // 集合处理完了就强制合并剩余的 run 到只剩下一个 run
    fn merge_force_collapse(&mut self) {
        let runs = &mut self.runs;
        while runs.len() > 1 {
            let n = runs.len() - 2;

            // 三个连续的 run: A、B、C，判断其长度关系并进行合并
            // n - 1 对应 A、 n 对应 B、n + 1 对应 C
            let (pos1, pos2) = if n > 0 && runs[n - 1].len < runs[n + 1].len {
                (n - 1, n)
            } else {
                (n, n + 1)
            };

            // 取出待合并的 run1 和 run2
            let (run1, run2) = (runs[pos1], runs[pos2]);
            debug_assert_eq!(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);
        }
    }
}

// timSort 入口