http://www.lifebackup.cn/timsort-java7.html
在Java 6中Arrays.sort()和Collections.sort()使用的是MergeSort,而在Java 7中,内部实现换成了TimSort,其对对象间比较的实现要求更加严格:
Comparator的实现必须保证以下几点(出自这儿):
a). sgn(compare(x, y)) == -sgn(compare(y, x))
b). (compare(x, y)>0) && (compare(y, z)>0) 意味着 compare(x, z)>0
c). compare(x, y)==0 意味着对于任意的z:sgn(compare(x, z))==sgn(compare(y, z)) 均成立
4.2) 传入的待排序数组若小于MIN_MERGE(Java实现中为32,Python实现中为64),则
a) 从数组开始处找到一组连接升序或严格降序(找到后翻转)的数
b) Binary Sort:使用二分查找的方法将后续的数插入之前的已排序数组
TimSort is a stable form of merge-sort algorithm invented by Tim Peters.
http://dertompson.com/2012/11/23/sort-algorithm-changes-in-java-7/
Method for Sorting Based on Binary Search
- Select an arbitrary element and add it to our sorted list, S.
- Select another arbirtrary element, x, and, using binary search, try to find x in S.
- Place x in S according to the results of the binary search.
- Repeat steps 2 and 3 until there are no more elements to select.