归并排序可以节省内存

首先，我会确保你理解归并排序。

看看这里的解释，里面有漂亮的动画帮助你理解它。

这是他们的伪代码版本：

＃分割成两半
m = n / 2

＃递归排序
sort a [1 .. m]
sort a [m + 1..n]

＃使用临时数组合并排序后的子数组
b = a [1..m]的副本
i = 1，j = m + 1，k = 1
while i <= m and j <= n，
    a [k ++] =（a [j] <b [i]）？ a [j ++]：b [i ++]
    →不变式：a [1..k]处于最终位置
while i <= m，
    a [k ++] = b [i ++]
    →不变式：a [1..k]处于最终位置

看看他们如何使用b来保存一份数据的临时副本？ 你的老师想要的是你传入一个表来用于这个临时存储。

这样清楚了这个任务吗？

你的主要排序程序看起来像这样：（抱歉，我不知道 Lua，所以我会写一些类似 Java 的代码）

void merge_sort(int[] array) {
  int[] t = ...分配临时数组...
  merge_sort_1(array, 0, array.length, t);
}

merge_sort_1 接受要排序的数组，一些起始和结束索引，以及用于一些临时空间的数组。它执行实际的分治调用和调用 merge 程序。请注意，递归调用需要调用 merge_sort_1 而不是 merge_sort，因为您不希望在每个递归级别上分配数组，而是只需在归并排序过程的开始处分配一次。（这就是将归并排序分成两个程序的全部意义。）

我会留给你编写一个 merge 程序。它应该接受包含 2 个已排序子部分的原始数组和一个临时数组，并对原始数组进行排序。最简单的方法是将其合并到临时数组中，然后在完成时只需将其复制回来。

首先，好吧，它是如何完成的？您是否只需在每个拆分和合并的递归中重写临时数组？

是的，临时数组会不断被覆盖。在合并阶段，临时数组用于保存合并结果，然后在合并结束时将其复制回永久数组中。

第二个问题很困惑，因为我不知道 merge_sort_1 应该做什么，为什么它必须是与 merge_sort 不同的方法。

merge_sort_1 是递归归并排序的递归中心。merge_sort 将作为一个方便的函数，创建临时数组并填充初始的开始和结束位置。

我也不知道为什么它需要传递起始和终止索引。实际上，也许我误读了一些东西，但是这些说明听起来好像 merge_sort_1 并没有做任何实际工作。

此外，整个任务很困惑，因为我从说明中看不出在哪里进行分割以使原始数组分为两半。或者我是否误解了归并排序？

递归函数 merge_sort_1 仅处理传入数组的一部分。它处理的部分由开始和结束索引定义。开始和结束之间的中点是分割数组的方式，然后在递归调用中再次分割。在完成上半部分和下半部分的递归调用后，将两个半部分合并到临时数组中，然后将其复制回永久数组中。

我能够按照描述写出 Lua 版本的归并排序，并可以对我的实现进行评论。似乎说明像是对教师实现的注释或评论。

这是 merge_sort 函数。正如我所说，它只是一个方便的函数，我认为它不是问题的关键。

-- Write a top level procedure merge_sort that takes as its argument
-- the array to sort.
function merge_sort(a)
    -- It should declare a temporary array and then call merge_sort_1,
    -- a procedure of four arguments: The array to sort, the one to use
    -- as temporary space, and the start and finish indexes within which
    -- this call to merge_sort_1 should work.
    merge_sort_1(a,{},1,#a)
end