证明合并排序输出输入的排列

Question

我开始研究计算逻辑，作为练习，我想证明合并排序算法的正确性。

目前，我很难证明该算法的输出将始终与给定输入的排列相对应。

如果有人可以帮助我，我会很高兴。

非常感谢😄

Answer 1

合并排序的先决条件是什么？职位条件是什么？你有循环不变式吗？

这是开始编写证明之前必须问自己的三个问题。

然后：您的基本情况是什么？大概您知道如果要处理证明时合并排序是如何工作的，那么当您将长度为1的数组传递给mergesort函数时会发生什么呢？那里的前提是什么？

这里是关于如何证明函数正确性的decent primer from Berkeley。编写证明可能需要一些离散的数学（归纳法）。