Сортировка сегментов даст вам алгоритм линейной сортировки по времени, при условии, что вы можете вычислить CDF каждой точки за O (1) времени.
Алгоритм, который вы также можете посмотреть в другом месте, выглядит следующим образом:
a = array(0, n - 1, []) // create an empty list for each bucket
for x in input:
a[floor(n * cdf(x))].append(x) // O(1) time for each x
input.clear()
for i in {0,...,n - 1}:
// this sorting step costs O(|a[i]|^2) time for each bucket
// but most buckets are small and the cost is O(1) per bucket in expectation
insertion_sort(a[i])
input.concatenate(a[i])
Время ожидания составляет O (n) в ожидании, потому что в ожидании есть O (n) пар (x, y), такие, что x и y попадают в один и тот же сегмент, а время выполнения сортировки вставки точно равно O ( n + # пар в одном ведре). Анализ аналогичен анализу статического хеширования FKS .
РЕДАКТИРОВАТЬ: Если вы не знаете распределение, но знаете, из какого он семейства, вы можете просто оценить распределение в O (n), в случае Гаусса, вычислив среднее значение и дисперсию, а затем использовать то же самое алгоритм (кстати, вычисление cdf в этом случае нетривиально).