Здравствуйте, ylp, Вы писали:

ylp>У квиксорта посимвольно получется O(p*N*logN), потому что квиксорт сравнитвет только общие префиксы строк.

Чушь. На самом деле — сравнение заканчивается на первом символе, который отличается. Если сравнивать только общие префиксы, то все строки будут равны (что очевидно для любого, кроме илпа)
И для радикс сорт — тоже. Сюрприииз! (на самом деле нет, я тебя это уже не первый раз повторял. Риталин уже купил?)

ylp>Это значит что две случайно выбранные сроки скорее всего вообще не будут иметь общий префикс.


Очередные чудеса вычислений, интересно где такому учат — в церковно-приходской школе?
На самом деле, компареру нужно будет сравнивать минимум один символ для каждой пары строк, и два и более — еще для какого-то процента пар.