将小规模无序数组合并到大规模有序数组的最优算法是什么

由于小规模数组长度k远小于大规模有序数组长度n，最优算法的核心逻辑固定为：先对小规模无序数组排序，时间复杂度为O(k log k)，再将两个有序数组合并，时间复杂度为O(n + k)，整体复杂度远低于直接将两个数组合并后重排的O((n+k)log(n+k))。

分场景适配方案 #

1. 缓存内排序场景（8MB有序数组 + 92KB无序数组） #

该场景下两个数组均可完全载入CPU缓存，优先追求极致执行效率：

• 对92KB的小数组执行快速排序，小数据量下快排的缓存友好性和执行效率优于其他排序算法
• 采用双指针法归并两个有序数组即可，所有操作均在缓存内完成，无缓存失效开销，整体耗时可控制在微秒级。

2. 内存内排序场景（2.5GB有序数组 + 3.9MB无序数组） #

该场景下两个数组均可完全载入系统内存：

• 先对3.9MB的无序小数组完成排序
• 允许额外内存存储结果时，优先用双指针顺序归并：顺序读取两个数组元素，按大小依次写入结果内存即可，内存顺序读写效率极高，2.5GB数据遍历仅需几十毫秒
• 要求原地合并时，可对小数组的每个元素在大数组中做二分查找确定插入位置，再移动大数组元素完成插入即可。

3. 外部排序场景（34GB有序数组 + 21MB无序数组） #

该场景下大规模数组无法全部载入内存，需借助外存存储：

• 先将21MB的无序小数组载入内存完成排序
• 采用分段归并方案：每次从大的有序数组中读取一段可载入内存的块，与小数组做双指针归并，将归并完成的结果顺序写回外存，重复该流程直到大数组全部块处理完成即可，整个过程仅需遍历大数组一次，完全利用外存顺序读写的高效率，避免随机读写开销。

内容的提问来源于stack exchange，提问作者Charles