假设我们有一个子程序可以对任何大小为 m 的列表进行就地排序。通过重复调用子例程，你能以多快的速度对大小为 2m 的列表进行排序？需要调用多少次子程序？
最佳答案
您大概可以通过 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
关于algorithm - 使用一次对 n 个元素进行排序的函数对 2n 个元素的数组进行排序，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/57413534/