timsort及最初版本的bug

#### 什么是timsort

Timsort is a hybrid stable sorting algorithm, derived from merge sort and insertion sort, designed to perform well on many kinds of real-world data. It uses techniques from Peter McIlroy’s “Optimistic Sorting and Information Theoretic Complexity”, in Proceedings of the Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 467–474, January 1993. It was implemented by Tim Peters in 2002 for use in the Python programming language. The algorithm finds subsequences of the data that are already ordered, and uses that knowledge to sort the remainder more efficiently. This is done by merging an identified subsequence, called a run, with existing runs until certain criteria are fulfilled. Timsort has been Python’s standard sorting algorithm since version 2.3. It is also used to sort arrays of non-primitive type in Java SE 7, on the Android platform, and in GNU Octave.
Worst-case performance : nlogn
Best-case performance : n
Average performance : nlogn
Worst-case space complexity O(n)

#### 步骤

1. 判断数组的大小，小于32使用二分插入排序
2. 数组大于32时，将输入按其严格升序和严格降序特点进行了分区（run），其中分区长度（runLen）过短则用插入排序补充到minRun的个数
3. 将run入栈，若栈中不满足runLen[i - 3] > runLen[i - 2] + runLen[i - 1]runLen[i - 2] > runLen[i - 1]那么就合并相邻较小栈，栈顶三元素满足则break，继续执行入栈操作
4. 栈只剩一个run时结束

#### BUG

BUG出现的地点正在这个条件里

120, 80, 25, 20, 30

120, 80, 45, 30