Задача сортировки - интервалы n / k размером k каждый

Question

Дан массив размером n , который был разделен на n / k интервалы размером k каждый.Значения в каждом интервале больше, чем в интервале слева и меньше, чем в интервале справа.Я хочу отсортировать эти значения за минимальное время, которое у меня есть.

Наивное решение, о котором я подумал, - просто отсортировать все значения в каждом интервале, которые будут «стоить» O (k log k) , для общей стоимости для всех n / k интервалов O (n log k) .Интересно, есть ли что-то более эффективное?

Теперь я знаю, что в каждом интервале у меня есть не более чем log log k разных значений, мне нужно придумать более быстрый алгоритм.Я буду рад вашей помощи с этим.

Спасибо!

Answer 1

Вот очень уродливый ответ:

1. Take the first interval;
2. Since logK should be small, we allocate logK binary tree nodes, and we place the first element in the middle;
3. For the rest of the elements, we use method similar to binary search to search if it is already included, or we add this element;
4. Produce a sorted list with all the values in the interval;
5. Use Counting Sort with this list on the interval;
6. Do this for all the intervals.

Время, используемое для 2,3, равно O (K * logloglogK), поскольку поиск занимает самое большее logloglogK (войти в элементы loglogK) и повторяется в течение K раз. 4 Используйте не более O (loglogK) времени для обхода всех узлов со значениями. 5 занимает время O (K), аналогично счетной сортировке. Таким образом, общее время должно быть O (nlogloglogK).

Любой вопрос приветствуется, так как я очень сонный и не могу гарантировать, что я думаю прямо.

Answer 2

Вы можете использовать сортировку подсчета или сортировку ведра на каждый интервал, стоимостью O(k) для каждого, с общей стоимостью O(n/k * k) = O(n)

Затем объединитькаждый интервал вместе стоит всего O(n).Тогда вашим алгоритмом будет алгоритм O(n) + O(n) = O(n).

Примечание: если вы можете использовать преимущества параллелизма, вы можете отсортировать все интервалы параллельно для общей стоимости O(k).Хотя ваш алгоритм по-прежнему будет O(n) (из-за слияния), он будет иметь меньшие постоянные коэффициенты.