考虑N个元素的未排序数组，其中每个元素都是字节大小的。假设缓存大小为1 KB，缓存行大小为64，再假设缓存是以完全关联的方式组织的，则在将合并排序算法应用于数组时计算缓存未命中的数量。在进行分析时，您可能需要考虑将数组大小N与缓存大小进行比较的不同情况。您是否对修改合并排序算法有什么建议，以减少缓存未命中。假设合并排序算法使用1个临时数组存储要合并的2个数组的元素。
似乎可以使用标准的自下而上的合并排序，而无需进行修改。
有（1024/64）= 16个缓存行。假设合并排序已达到一个点，此时已排序的运行大于64个字节。在合并操作期间，将使用2条缓存行来合并2个要排序的运行，并使用1条缓存行来合并输出。高速缓存未命中只会每64个字节读或写一次。
自下而上的合并排序将生成大小为2的幂的排序运行，这可能对缓存更友好。
我不确定修改中允许的合并排序。使用混合插入排序+合并排序可以减少排序时间。令k =＃要通过插入排序进行排序的元素，以创建大小为k的排序运行。一个简单的实现是确定基本的自底向上合并排序所需的排序通过次数：passcount = ceil（log2（N））。如果通过次数为奇数，则使用k = 32，如果通过次数为偶数，则使用k =64。这将导致合并排序遍数为偶数，这可以在每次合并遍历上交替合并方向，从而避免了在复制过程中必须复制数据合并步骤。
假设合并排序算法使用1个临时数组存储要合并的2个数组的元素。
这部分不太清楚。一次性分配与要排序的数组大小相同的临时数组，然后对合并操作使用相同的索引，这样效率更高。效率较低的方法是为每个合并操作分配一个临时数组，该数组的大小与要合并的两个排序运行的大小之和相同，这需要复制到（如果在合并之前）或从（如果在合并之后）复制临时数组。如前所述，合并操作可以基于自下而上的合并遍历或递归的自上而下的递归级别来更改合并的方向，以避免复制数据。