链表合并排序解释

Question

有人能给我解释一下这段代码是如何工作的吗：

http://www.chiark.greenend.org.uk/~sgtatham/algorithms/listsort.c

我不理解这篇文章中使用的算法。谢谢

Answer 1

尝试想象在一个数组上执行的所有合并:首先，将元素配对并合并到长度为2的已排序子数组中，然后将这些长度为2的子数组配对并合并到长度为4的已排序子数组中，依此类推。注意子数组的长度: 1、2、4，依此类推，让我们将其称为instep，它在每次迭代中加倍。

在任何时候，p指向长度为instep的列表，q指向长度为instep或更小的列表(我们可能到达列表的末尾)，q紧跟在p之后。如上所述，它们形成了一对子数组。我们对p和q进行合并，以获得从p开始的长度psize + qsize的排序列表。然后我们将p和q移动到下一对，依此类推。一旦我们完成了整个列表，我们加倍instep并开始合并更长的排序列表。