stable algorithm with complexity O(n)
Terry Reedy
tjreedy at udel.edu
Mon Dec 15 13:30:08 EST 2008
Dan Upton wrote:
> And if n is small and sparse (ie, k > n) , O(k*n) for radix sort could
> be worse than O(n^2). You could also ask why people make such a big
> deal about quicksort over mergesort, since mergesort has a guaranteed
> O(n log n) time whereas quicksort can be O(n^2) on pathological cases.
Python's current list.sort uses mergesort because it better exploits
existing structure in a list.
> I think I remember learning in my algorithms class that for small
> sorts (n < ~40) , bubblesort can actually be the fastest (or close to
> the fastest) in terms of wall-clock time because it has a relatively
> small constant factor in its O(n^2) complexity.
It uses binary insert sort for n < 64 (chosen empirically) . That also
does O(n logn) comparisons and is only O(n**2) for data movement, which
a decent C compiler translates into fast block-move assembly instructions.
tjr
More information about the Python-list
mailing list