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. -- http://mail.python.org/mailman/listinfo/python-list
