Нека имаме n на брой думи с обща дължина m. Под линейно време ще разбираме O(m). Това е общата големина на входа, за която обаче няма строго съответствие с броя елементи - разлика с масивите с числа, например - заради което двете големини се разглеждат поотделно.

Нека създадем празен Trie (чете се "трай") и вмъкнем всяка дума от списъка в него. Заради особеността на тази структура вмъкването на дума в нея отнема време и памет, линейни по големината на тази дума, без значение от броя вече съдържани други думи (!) => вмъкването на всички ще отнеме общо O(m) време и допълнителна памет. Б.о.о. можем да допуснем, че възлите в това дърво пазят наследниците си подредени - например с масив от указатели, в който първият съответства на буквичката 'a', вторият на 'b' и т.н. Аналогът на обхождане корен-ляво-дясно в такова дърво първо би посетило наследника с 'a' (ако съществува), после с 'b' и т.н. преди да се върне нагоре по рекурсивните извиквания. Това обхождане би отнело също O(m) време и памет и с него ще получим думите от първоначалния списък в лексикографска наредба, за общо време и допълнителна памет O(m) - линейни по големината на входа.

Как се използва за числа - можем да си представяме неотрицателните* числа като "думи" от битове, всяка с дължина lgn бита. Тогава m = nlgn и получаваме отново O(nlgn) алгоритъм за сортиране на числа, въпреки че не използва директни сравнения.

Заб.: алгоритъмът има голяма теоретична полза, както и връзка с много други алгоритми и структури от данни за стрингове. На практика обаче е неефективен заради огромното количество допълнителна памет (възлите в дървото са O(n), но заемат по много памет), както и относително бавното траверсиране на дървото (hint: cache/memory locality)

*Ако имаме отрицателни числа, то можем предварително да "изместим" всяко число в списъка така, че да станат неотрицателни, и да ги възстановим след сортирането.