合并排序如何处理长度为 N 的数组？

Question

我读过书，遇到了无法解决的问题。我查了很久的资料。我绞尽脑汁试图理解它。

因此，我得到一个长度为 N (int) 的数组，通过使用非递归合并排序算法对其进行排序。我学习了长度为 2^n 的数组的合并排序算法。但我完全不明白它对于长度为 N 的数组是如何工作的。

有人可以解释一下它是如何工作的吗？

Answer 1

给定七个元素，子任务树如下所示：

          [3,5,2,1,4,7,6]
             /         \
      [3,5,2,1]        [4,7,6]
      /       \        /      \
   [3,5]    [2,1]    [4,7]    [6]
   /   \    /   \    /   \    /
 [3]  [5]  [2]  [1] [4]  [7] [6]

这个想法是在每个级别将数组“分成两半”。如果一个数组有奇数个项目，则将其拆分将导致一个子数组比另一个子数组多一个项目。它不会使问题变得更加困难：合并两个不同长度的数组并不麻烦。