This article makes extensive use of Big-O notation.

n is the number of elements to be sorted
k is the key size in bits; the smallest k for n uniquely identified elements is log(n)

I was taught in school (back in the day) that general sorting, usually assumed to be comparison sorting, is O(n × log(n)).

An alternative and well-known form of sorting, radix sort, which places elements relative to the value of the key rather than swapping after comparisons, is O(k × n). Since the smallest-case k for a set of uniquely identified elements is log(n) bits, O(n × log(n)) for radix sorting is still accurate for a smallest-case key size.

However, in comparison sorting analysis the key size is often ignored and the comparison time is assumed constant. Thus the fastest comparison sorts are O(n × log(n)) comparisons. If the same strategy were applied to the analysis of radix sort, its time complexity would be O(n) — k would be a constant factor.

Given that most general-purpose comparison sort algorithms accept arbitrary objects with arbitrary comparators, comparison time is certainly not constant. If arbitrary key size is considered, sort time for comparison sorts would be O(k × n × log(n)) or, for the smallest-case k, O(n × log²(n)).

Radix sort doesn’t readily handle arbitrary data-types — typically used for sorting of fixed-size integers. The argument is that since radix sort isn’t general, its performance doesn’t translate to general sort performance.

What is general sorting? Any data structure that can be represented in computer memory can also be represented as a string, or a loosely-structured, arbitrarily-long sequence of bytes. So string sorting is general sorting.

There is a string sorting algorithm, Burstsort, that efficiently sorts strings and is O(k × n), where k is the average key size. As mentioned above, strings can represent arbitrary data structures, so Burstsort is general for sorting. A general implementation of Burstsort would take a set of objects and a serializing function as input rather than a comparator. The serialization of the objects to be sorted may not be particularly fast, but it is O(k × n).

Therefore, general sorting is O(k × n). Since that’s also the minimum time required to at least look at the keys to be sorted, general sorting is also Θ(k × n).

I’m not sure if this is old news to everyone, but it only just hit me.