arrays - 对三个数组的元素进行排序的算法

Question

这是难点:

Start with three arrays A, B and C with a total of 2n+1 entries. Write an algorithm to sort all of the entries from all of the arrays using only the following two methods:

1. X = sort(X) replaces the array X with the sorted version.

2. (X , Y) = doubleUp(X , Y) does nothing if X has more elements than Y, otherwise it removes the first length(X) entries from Y and appends them to the end of X.

这是我到目前为止尝试过的方法。如果其中两个数组为空，则只需对非空数组使用 sort。

如果其中一个数组是空的，那么我想我可以使用 doubleUp 来让一个数组只包含一个元素，而另一个数组包含所有其他元素，如果那个单例数组有最小(或最大)元素，那么就可以了。所以我可以在每次使用 doubleUp 之后使用 sort 来确保发生这种情况。我在 Maple 中对此进行了编码，它适用于我检查过的所有情况。

虽然我不知道如何使用 3 个数组来完成。有人有什么想法吗？

Answer 1

听起来像废话。条目总数是奇数。增加数组长度的唯一方法是使其成为 doubleUp 的较小的第一个参数，在这种情况下它以偶数个元素结束。因此，除非所有元素一开始都在一个数组中，否则无法使一个数组包含所有元素，无论是排序的还是其他方式。

因此，所需的最终结果不是按顺序包含所有元素的单个数组。或者，如果是，则问题的答案是“无法完成”。