两个任意大小的排序列表的奇偶合并
我有以下场景：我得到两个（以前）排序的数字序列，我需要使用合并网络（例如批处理程序的 http://bit.ly/ytbmqE）。然而，这些网络被设计用于 2^k 大小的序列，这不是我的情况。
谁能建议一种方法来做到这一点？理想情况下，不会强制列表的大小为 2 的倍数（例如在开头附加零）。
I have the following scenario: I am given two (previously) sorted sequences of numbers and I need to merge them using a merging network (such as batcher's http://bit.ly/ytbmqE). However, these networks are designed to work for sequences of 2^k size, which is not my case.
Can anyone suggest a way to do that? Ideally one that doesn't involve forcing the list to be of some size that is a multiple of 2 (such as by appending zeroes to the beginning for instance).
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（3）
您的输入数组的大小为 x，如果它不是 2t 的格式，它将为： 2ttttt x<2t+1，因此您可以将 2t+1 - x 具有最大值的元素添加到您的输入中（使其成为最两次），然后应用一个公共网络进行排序。最后从结果中删除最后 2t+1 - x 元素。
Your input array is of size x and if it's not in the format of 2t it will be as: 2t< x<2t+1, so you can add 2t+1 - x elements with max value to your input (makes it as most twice) and then apply one of a common network for sorting. and finally remove last 2t+1 - x elements from your result.
我认为你有两个选择，但我可能是错的：
填写-99999或99999，在你的最终结果中忽略99999的尾部。
用 null 填充，并且在每次比较中允许 null 在 try catch 异常语句中丢失。根据您的语言，您可能仍然需要从数据结构中去除尾部的空值。
编辑：
有一种方法可以不使用填充值来做到这一点，但它需要多次合并。例如，合并两个列表的子集，然后取出其中一些数字并将它们与您第一次遗漏的数字混合，然后再次合并两个列表，然后合并上半部分和下半部分..输入内容..有点乱。
I think you have two choices but i could be wrong:
Fill with -99999 or 99999 and in your end result ignore the tail of 99999's.
Fill with nulls, and in each comparison allow null to lose in a try catch exception statement. Depending on your language you may still need to strip the tail of nulls from your data structure.
EDIT:
There is a way to do it without using fill values, but it requires multiple merging. E.g. merge a subset of the two lists, then take some of these numbers and mix them with the numbers you left out the first time, and then merge two lists again, then merge the top halfs and the bottom halfs .. type thing.. kinda messy.
取大于输入大小的二的最小幂的网络，并删除所有涉及不存在元素的比较器。
Take the network for the least power of two greater than the input size and delete all of the comparators that involve non-existent elements.