sorting - 当必须对小数组进行排序*和*复制时，替代插入排序+复制

Question

考虑两个长度为 N 的数组 A 和 B，其中 N 相当小。我想对 A 中的元素进行排序并将排序后的元素存储在 B 中。

在 A 上进行就地插入排序，然后将排序后的值批量复制到 B 将相当简单。但是，这无法利用两件事：

1. 有大小为 N 的暂存空间可供使用，并且
2. 排序后的值最终需要在 B 而不是 A 中结束。

谁能提出不同的方法（可能是修改后的插入排序？），以利用其中一个（或两者）并最终胜过插入排序+复制的简单解决方案？

Answer 1

多年后进来，但如果其他人抓住这个机会，这是我的两分钱。将插入排序与合并排序等快速异地排序结合使用可能会提供一些最小的改进。

1. 将数组分成四等份并使用插入排序进行排序
2. 将第一和第二季度合并到暂存空间，第三和第四季度相同
3. 从头开始将前半部分和后半部分合并到目标数组中

同样，这可能提供最小的现实世界改进，并且可能是过早优化的情况。你最好对你的应用程序进行基准测试，看看你是否真的需要改进这部分算法，或者你的时间是否最好花在优化其他东西上。