More Efficient Sorting Algorithms

Still, why is list.sort so much more efficient? The answer is the same as it was for binary search: t takes advantage of the fact that some values are already sorted.

A First Attempt

Consider the following function:

​	​import​ ​bisect​
​
​	​def​ ​bin_sort​(values: list) -> list:
​	​"""Return a sorted version of values. (This does not mutate values.)​
​
​	​ >>> L = [3, 4, 7, -1, 2, 5]​
​	​ >>> bin_sort(L)​
​	​ [-1, 2, 3, 4, 5, 7]​
​	​ """​
​
​	result = []
​	​for​ v ​in​ values:
​	bisect.insort_left(result, v)
​
​	​return​ result

This code uses bisect.insort_left to determine where to insert each value from the original list into a new list that is kept in sorted order. As you have already seen, doing this takes time proportional to log₂N, where N is the length of the list. Since N values need to be inserted, the overall running time should be N log₂N. As shown in the following table, this growth rate is significantly slower than N² with the list length.

N	N2	N log2N
10	100	33
100	10,000	664
1000	1,000,000	9965

Unfortunately, there’s a flaw in this analysis. It’s correct to say that bisect.insort_left requires only log₂N time to determine where to insert a value, but inserting it takes additional time. To create an empty slot in the list, you must move all the values above that slot up one position. On average, this means copying half of the list’s values, so the cost of insertion is proportional to N. Since there are N values to insert, your total time is N*(N + log₂N). For large values of N, this is once again roughly proportional to N².

Отправить