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

Question

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

对 A 执行就地插入排序，然后将排序后的值批量复制到 B 是相当简单的。 但是，这未能利用两件事：

1. 有 N 号的暂存空间可供使用，并且
2. 排序后的值最终需要以 B 而不是 A 结尾。

任何人都可以提出不同的方法（可能是修改后的插入排序？）来利用其中的一种（或两种）并最终优于插入排序+复制的简单解决方案？

Answer 1

多年后才进来，但如果其他人有机会，这是我的两分钱。将插入排序与快速错位排序（如合并排序）结合使用可能会提供一些最小的改进。

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

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