нечетно-четное объединение для двух отсортированных списков произвольных размеров

Question

У меня следующий сценарий: мне даны две (ранее) отсортированные последовательности чисел, и мне нужно объединить их, используя объединяющуюся сеть (например, дозатор http://bit.ly/ytbmqE).. Однако эти сети предназначены для работы с последовательностями размером 2 ^ k, что не в моем случае.

Может кто-нибудь предложить способ сделать это? В идеале такой, который не требует, чтобы список был некоторого размера, кратного 2 (например, путем добавления нулей к началу).

Answer 1

Ваш входной массив имеет размер x, и если он не в формате 2 ^t , он будет иметь вид: 2 ^t t + 1 , так что вы можете добавить 2 ^{t + 1} - x элементов с max значением к вашему входу (делает его как минимум два раза) и затем применить одну из общей сети для сортировки. и, наконец, удалите последние 2 ^{t + 1} - x элементов из вашего результата.

Answer 2

Возьмите в сеть наименьшую мощность в два раза больше входного размера и удалите все компараторы, которые содержат несуществующие элементы.

Answer 3

Я думаю, у вас есть два варианта, но я могу ошибаться:

1. Заполните с -99999 или 99999 и в конечном результате проигнорируйте хвост 99999.

2. Заполнить нулями, и в каждом сравнении разрешить ноль проигрывать в операторе исключения try catch. В зависимости от вашего языка вам все равно может понадобиться убрать хвост из нулей из вашей структуры данных.

EDIT:

Есть способ сделать это без использования значений заполнения, но он требует многократного объединения. Например. объедините подмножество двух списков, затем возьмите некоторые из этих чисел и смешайте их с числами, которые вы пропустили в первый раз, а затем снова объедините два списка, затем объедините верхние и нижние половинки .. наберите вещь .. вроде грязный.