Sorts

[Peter Schneider-Kamp]

Robin Porter wrote:
> 
> Does anyone know what type of sort is used for the internal sort
> function in Python (quick, merge, insertion, etc.)?

The following assumes that we talk about lists in the standard
(C) Python edition.

binary insertion sort is used for small lists (<100 elements) whereas
a quicksort derived sorting algorithm called "samplesort" is used for
larger lists. A description can be found in the list object
implementation:

   samplesort is basically quicksort on steroids:  a power of 2 close
   to n/ln(n) is computed, and that many elements (less 1) are picked at
   random from the array and sorted.  These 2**k - 1 elements are then
   used as preselected pivots for an equal number of quicksort
   partitioning steps, partitioning the slice into 2**k chunks each of
   size about ln(n).  These small final chunks are then usually handled
   by binarysort.  Note that when k=1, this is roughly the same as an
   ordinary quicksort using a random pivot, and when k=2 this is roughly
   a median-of-3 quicksort.  From that view, using k ~= lg(n/ln(n))
makes
   this a "median of n/ln(n)" quicksort.  You can also view it as a kind
   of bucket sort, where 2**k-1 bucket boundaries are picked
dynamically.

   The large number of samples makes a quadratic-time case almost
   impossible, and asymptotically drives the average-case number of
   compares from quicksort's 2 N ln N (or 12/7 N ln N for the median-of-
   3 variant) down to N lg N.

quite-a-hack-ly y'rs Peter
--
Peter Schneider-Kamp          ++47-7388-7331
Herman Krags veg 51-11        mailto:peter at schneider-kamp.de
N-7050 Trondheim              http://schneider-kamp.de