Эффективность поразрядной сортировки

Рост быстрой сортировки мы уже знаем: O(nlogn). Судя по оценке, поразрядная сортировка растет линейным образом по n, так как k,m - константы.
Также она растет линейным образом по k - при увеличении длины типа(количества разрядов) соответственно возрастает число проходов. Однако, в последний пункт реальные условия вносят свои коррективы.
Дело в том, что основной цикл сортировки по i-му байту состоит в движении указателя uchar* bp шагами sizeof(T) по массиву для получения очередного разряда. Когда T=char, шаг равен 1, T=short - шаг равен 2, T=long - шаг равен 4... Чем больше размер типа, тем менее последовательный доступ к памяти осуществляется, а это весьма существенно для скорости работы. Поэтому реальное время возрастает чуть быстрее, нежели теоретическое.

Кроме того, поразрядная сортировка уже по своей сути неинтересна для малых массивов. Каждый проход содержит минимум 256 итераций, поэтому при небольших n общее время выполнения (n+m) определяется константой m=256.

Поведение неестественно, так как проходы выполняются полностью, вне зависимости от исходного состояния массива. Поразрядная сортировка является устойчивой.