TimSort 中的核心过程
TimSort 是 Python 中 list.sort 的默认实现。Java 7 也将非原始类型列表的排序实现替换成了 TimSort。网上关于 TimSort 是什么，性能特点分析的文章不少，但是介绍它的具体实现步骤的文章很少。这里有一篇：Understanding timsort, Part 1: Adaptive Mergesort，用 C 作为示例代码。

基于这个文章的介绍，我用 python 实现一遍 TimSort，并说一下其中的关键步骤。因为原文只讲解了 TimSort 中最基本最重要的部分，所以本文也没有超过这个范围。本文不是对 TimSort 的分析，只是介绍一下其基本实现。

TimSort 概览
TimSort 是一个归并排序做了大量优化的版本。对归并排序排在已经反向排好序的输入时表现O(n^2)的特点做了特别优化。对已经正向排好序的输入减少回溯。对两种情况混合（一会升序，一会降序）的输入处理比较好。

TimSort 核心过程
假定，我们的 TimSort 是进行升序排序。TimSort 为了减少对升序部分的回溯和对降序部分的性能倒退，将输入按其升序和降序特点进行了分区。排序的输入的单位不是一个个单独的数字了，而一个个的分区。其中每一个分区我们叫一个“run“。针对这个 run 序列，每次我们拿一个 run 出来进行归并。每次归并会将两个 runs 合并成一个 run。归并的结果保存到 "run_stack" 上。如果我们觉得有必要归并了，那么进行归并，直到消耗掉所有的 runs。这时将 run_stack 上剩余的 runs 归并到只剩一个 run 为止。这时这个仅剩的 run 即为我们需要的排好序的结果。

如何合并
    那么何时进行合并？合并的策略是要在 "run_stack" 上维护一个不变式。当这个不变式被打破时即进行合并。传统的归并排序通过二分法可以保证函数栈的深度为 log(n)。我们也模拟这个策略，也让 run_stack 的长度不超过 log(n)。假如 runN 先入栈，runN+1 紧随其后入栈。那么就要求 runN 的长度要是 runN+1 长度的 2 倍。所以归并的条件是：如果 runN 的长度 < (runN+1 的长度 * 2) 即进行归并。