algorithm - 使用一次对 n 个元素进行排序的函数对 2n 个元素的数组进行排序

Question

假设我们有一个子程序，它将对任何大小为 m 的列表进行适当的排序。通过重复调用子程序，你能多快对大小为 2m 的列表进行排序？需要调用多少次子程序？

标签： algorithmsorting

Answer 1

您可能可以通过 5 次调用来完成此操作。我试图证明这一点，我没有做所有的细节，但这似乎是可能的。请注意，此解决方案需要重新排列（显然，不进行比较）元素。我不确定这是否被允许。

8 7 6 5 4 3 2 1
   sort each half (2 calls)
5 6 7 8 1 2 3 4
   sort the smaller halves (5 6 1 2) and larger halves (7 8 3 4) of each half (2 calls)
1 2 5 6 3 4 7 8
   sort the middle half (1 call)
1 2 3 4 5 6 7 8