stable algorithm with complexity O(n)

Lev Elbert elbertlev at
Sun Dec 14 06:53:17 CET 2008

1. Comparison sorts have n*ln(n) complexity - does not do
2. Counting sort has the complexity O(d), where d is domain (in our
case n^2) - does not do.
3. Radix sorts have the complexity O(n*k), where k is number of bits
in integer. (32?) There are 2 variants:
a. most significant digit (MSD),
b. least significant digit (LSD).

The LSD radix sort is stable.

Good luck.

More information about the Python-list mailing list