Скорость методов сортировки с K при сортировке мультимножества с K уникальными значениями

Question

Предположим, у меня есть большой мультимножество размера N, где элементы принимают значения из меньшего набора {1, ..., K}.Как время вычисления алгоритма сортировки масштабируется с K при N как фиксированном?

Я написал что-то на R, и кажется, что он масштабируется с линеарностью K.

x = sample(10, 1e6, replace = TRUE)
system.time(sort(x))
x = sample(100, 1e6, replace = TRUE)
system.time(sort(x))
x = sample(1000, 1e6, replace = TRUE)
system.time(sort(x))