Re:Assumptions assumptions! (Score 1)

When you say 'm is a small constant' you are again making a totally inappropriate assumption about limiting the key field size. When you make that assumption you're no longer allowed to use the O() operator because it is solely defined in the asymptotic case where all relevant variables are increased towards infinity, including m.

Perhaps I wasn't very clear with my intended definition of m. If the key field is 16 bits, then M is 2^16, not 16.

Anyway, switching to your intended definition of m, O(m) still must equal or exceed O(ln(n)) in order to have a unique sorting order. The execution time is O(m * n), which still equals or exceeds O(ln(n)*n) no matter how you slice it.