timsort

• timsort 对反序，和基本有序的数据处理较原来的merge sort要快很多(5倍左右)。
• 内部在对小分组情况下进行二分插排 binary_search，在选择小组的时候判断是否有序，有序或者倒序的情况是直接分成一组的。

skip list 跳表:

• 实现简单，性能与堆排序相近，且分段性能好，在并发开发上要优于 堆排序。ConcurrentSkipListMap (java 并发类)

二分插排

• 较为有序的时候比较占优势

快排

• 快排的使用范围是在随机性较强的时候占优势。

``

def do_when_end(array, begin, forward, reverse):
	if forward >= reverse:
	    array[begin], array[forward] = array[forward], array[begin];
	    return True;
	return False;

def find_right_place(array, begin, end):
	value = array[begin];
	forward = begin;
	reverse = end;
	while True:
    	while forward < reverse and value < array[reverse]:
    	    reverse -= 1;
   	 if do_when_end(array, begin, forward, reverse):
            return forward;
        while forward < reverse and value >= array[forward]:
            forward += 1;
        if do_when_end(array, begin, forward, reverse):
            return forward;
        array[forward], array[reverse] = array[reverse], array[forward];

def quick_sort(list,begin,end):
    if begin < end:
        forward = find_right_place(list, begin, end);
        quick_sort(list, begin, forward - 1);
        quick_sort(list,forward + 1,end);

if __name__ == "__main__":
    list = [1, 6,14,-1,-3,17,100,-9,-29]
    quick_sort(list,0,len(list) - 1)
    print(list);

``