stable algorithm with complexity O(n)

[Lev Elbert]

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.