Radix sort (and its variant trie sort) are the biggest ones: https://en.wikipedia.org/wiki/Radix_sort https://en.wikipedia.org/wiki/Radix_sort The O(n log n)

Radix sort (and its variant trie sort) are the biggest ones: https://en.wikipedia.org/wiki/Radix_sort https://en.wikipedia.org/wiki/Radix_sort The O(n log n) lower bound is only for comparison based sorts. If you don't take a comparison function, but instead look at the internal structure, you can do better, but of course that depends on that internal structure and what order you want them in.