Выбор самого быстрого алгоритма для сортировки данных действительно зависит от сортируемых данных.
Вы можете использовать сортировку подсчета, которая занимает O(N + R); где R - диапазон значений. Следовательно, чем больше диапазон элементов, тем больше время увеличивается.
Или Быстрая сортировка. Самый быстрый из возможных способов сортировки массива данных состоит в том, чтобы просто отсканировать данные, что даст вам N выбор для первого элемента. , N - 1 выбор для второго элемента и так далее до последнего элемента, который будет иметь только 1 выбор. Это заканчивается алгоритмом сортировки, который можно сделать в O(N!). N! может быть приближено к 2^(N * log N); поэтому быстрая сортировка выполняется в O(N * log N).
Не существует возможных алгоритмов сортировки, которые можно сортировать быстрее, чем O(N * log N).
Уловка для более быстрой сортировки заключается в использовании бесконечного числа процессоров, что может снизить сложность времени до 0(log N), но для больших N вы можете увидеть, как это не практично.
Или можно использовать log N процессоры, работающие параллельно, чтобы довести временную сложность до O(N). Но опять же, параллельная обработка - это больше хитрости, чем чего-либо еще. Сам алгоритм не сжат до O(N).