[Tutor] Sorting algorithm?

[Tim Peters]

[VanL]
> What sorting algorithm is used to sort lists?
>
> given
> >>> list = ['base', 'ball', 'mound', 'bat', 'glove', 'batter']
> >>> list.sort()
> >>> print list
> ['ball', 'base', 'bat', 'batter', 'glove', 'mound']
>
> What happens behind the scenes?  Quicksort, a la Perl? or some other
> algorithm, possibly depending on the size of n?

It's a hybrid algorithm, using binary insertion sort on "small" slices and
samplesort on "large" slices.  samplesort is an extreme variation of
quicksort, that reduces the asymptotic number of expected compares down to N
* log2(N).  This makes the expected number of compares comparable to
mergesort (close to the theoretical minimum), but samplesort requires far
less data movement than mergesort.  Compares are expensive in Python, so
minimizing compares is the primary goal for a Python sort.

Sorry there isn't an easy answer, but Python's .sort() method is in fact
complicated.  A long time ago, Python *did* use the platform C library's
qsort() function, but that was much slower, and on some platforms had bugs we
couldn't worm around.