Итак, я наткнулся на алгоритмы сортировки без сравнения, если быть точным, и я не мог точно понять, почему это хорошо.
У меня есть мысль, но мне нужен кто-то, чтобы подтвердить это.
Предположим, я хочу отсортировать массив из 1000 элементов. Если бы он был равномерно распределен и разделен на 10 сегментов, где в каждом сегменте было 100 элементов.
сортировка 100 элементов 10 раз с использованием алгоритма n log(n) = 10 * 100 log(100) = 1000 log(100) = 2000
при сортировке 1000 элементов с использованием алгоритма n log (n) = 1000 log (1000) = 3000
Таким образом, алгоритм использует, что если n = m + l, то (m + l) ^ 2 > m ^ 2 + l ^ 2, и то же самое относится к алгоритмам n log (n).
таким образом, чем более равномерно сегментированы данные, тем выше производительность сортировки сегментов.
Это правильно ?
и какое будет оптимальное количество ведер? (Я чувствую, что это компромисс между пространством и временем, но также зависит от однородности сортируемых данных)
