Practical Programming, 3rd Edition

More Efficient Sorting Algorithms

The analysis of selection and insertion sort begs the question, how can list.sort be so much more efficient? The answer is the same as it was for binary search: by taking 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 the 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 figure out where to put each value from the original list into a new list that is kept in ...