Понимание и решение слияния K-Way

Question

Am до

1) подсчитайте количество сравнений, необходимых для сортировки слиянием k-Way для сортировки случайной перестановки чисел от 0 до N-1.

2)

для подсчета количества перемещений данных, необходимых для сортировки слиянием K-Way o сортировки случайной перестановки чисел от 0 до N-1.

Я понимаю, как работает двусторонняя сортировка слиянием, и понимаю кодотлично.Моя проблема сейчас в том, что я не знаю, как начать, и мне нужна небольшая помощь.Как мне преобразовать сортировку с двухсторонним слиянием в K-Way, чтобы я мог решить вышеуказанные проблемы.

Я некоторое время гуглял, но не могу найти учебник, который бы помог мне понять "k-Wayсортировка слиянием "очень хорошо.

Мне нужно хорошее объяснение, что нужно сделать, чтобы я мог взять это оттуда и сделать это сам.

Как я уже сказал, я понимаю, что Двусторонний, таккак перейти к сортировке слиянием K-Way?Как мне реализовать K-way.

Спасибо за помощь.

РЕДАКТИРОВАТЬ

** Я прочитал какой-то пост http://bchalk.com/work/view/k_way_merge_sortэтот BinaryHeap должен использоваться для реализации слияния k-Way.Это так или есть другие способы?

** Как мне разделить мой список на K?Есть ли особый способ сделать это?

Answer 1

Когда k > 2, ведущие элементы каждого из входных потоков обычно хранятся в структуре minheap.Это позволяет легко найти в минимуме n-значений, извлечь это значение из кучи и вставить заменяющее значение из соответствующего входного потока.

Куча выполняет O(lg2 k) сравнения для каждоговставка, поэтому общая работа для k-way слияния n элементов составляет n * lg2(k).

Даже если вы спросили о C # и Java, вы можете узнать, как это сделать, взглянув на код стандартной библиотеки Pythonk-way merge: http://hg.python.org/cpython/file/2.7/Lib/heapq.py#l323

Чтобы ответить на ваш другой вопрос, нет особого способа разделить ваш список на K групп.Просто возьмите первые N / k элементы в первом массиве, следующие N / k элементы в следующий и т. Д. Сортируйте каждый массив и затем объедините их, используя кучи, как упомянуто выше.

Answer 2

Вы всегда можете думать о k-way merge как о последовательности двухсторонних слияний, то есть делать двухстороннее слияние с результатом первого и второго и третьего: Merge(Merge(L1, L2), L3) и так далее,Еще быстрее было бы разделить его дважды: Merge(Merge(L1, L2), Merge(L3, L4)).Как вы можете видеть, для k-way сортировки вам потребуется цикл (рекурсия).