TimSort算法

TimSort使用了”run“的概念,一个run是数组中单调上升或者严格单调下降的连续子数组。

  1. 数据规模小于32,则先求出第一个run的长度,然后用二分插入排序

  2. 数据大于等于32,则求出最小的run长度–> min_run,求此长度的策略是:数组长度是n,如果n<32,则直返返回n。 如果n>32,且n是2的幂数,返回16,否则返回k,16<=k<=32

  3. 求出min_run之后,从头开始求出每一个run的长度,每一个run必须大于等于min_run,否则用插入排序增加到min_run的长度 然后把这个run加入到

Written on April 4, 2019