我有一个关于数组合并排序如何工作的问题。 我理解‘Divide’步骤，它将一个输入数组分成1个长度的元素。然而，当谈到‘合并’部分(合并步骤)时，我就糊涂了。 例如，给定输入3 5 1 8 2，除法过程将产生5个元素：3，5，1，8，2。我只了解合并函数会将它们组合为3 5，1 8，2，但它如何继续组合3 5和1 8？‘Combine’部分中是否涉及递归？
推荐答案当两个递归排序例程返回时，您可以安全地假定它们已经对其各部分进行了排序。合并步骤组合这两个排序的子数组。如果输入为3 5 1 8 2，则第一个递归调用对前半部分进行排序并生成3 5，第二个递归调用对后半部分进行排序并生成1 2 8。
您询问的合并步骤，通过重复选择两个子数组的前两个元素中的最小值并将其添加到结果中，将这两个排序的一半合并为一个，如下面的动画所示：