Editing Radix sort (section)

== Complexity and performance ==
Radix sort operates in <math>O(n \cdot w)</math> time, where <math>n</math> is the number of keys, and <math>w</math> is the key length. LSD variants can achieve a lower bound for <math>w</math> of 'average key length' when splitting variable length keys into groups as discussed above.

Optimized radix sorts can be very fast when working in a domain that suits them.<ref>{{Cite web |first1=Ranjan |last1=Sinha |first2=Justin |last2=Zobel |title=Efficient Trie-Based Sorting of Large Sets of Strings| citeseerx=10.1.1.12.2367 |url=https://citeseerx.ist.psu.edu/pdf/15b4e7759573298a36ace2f898e437c9218cdfca |access-date=August 24, 2023}}</ref>
They are constrained to lexicographic data, but for many practical applications this is not a limitation. Large key sizes can hinder LSD implementations when the induced number of passes becomes the bottleneck.<ref name="auto"/>