13.7　添加递归

确定方法 merge 能够正确地运行后，就可尝试开发合并排序算法的版本了：

public Deck almostMergeSort() {
    // 将Deck对象一分为二
    // 用selectionSort对这两部分分别排序
    // 合并两部分并返回结果
}

本章末尾有个练习，要求你实现这种算法。正确实现该算法后，有趣的部分就开始了！合并排序的神奇之处在于，它天然就是递归的。

将各部分排序时，为何要调用较慢的算法 selectionSort 呢？为何不调用你正在编写的 mergeSort 呢？这不仅是个不错的主意，要想获得 log₂ 性能优势，你也必须这样做。

要让 mergeSort 递归地运行，必须添加基线条件，否则将没完没了地递归。一个简单的基线条件是有一部分没有牌或只包含 1 张牌。mergeSort 收到这样小的部分时，可原封不动地将其返回，因为它已经是排好序的。

递归版 mergeSort 应类似于下面这样：

public Deck mergeSort() {
    // 如果Deck对象中没有牌或只包含一张牌，就原封不动地返回它
    // 将Deck对象分成两部分
    // 用mergeSort分别对这两部分排序
    // 合并这两部分并返回结果
}

与通常情况一样，你也可以用两种方式研究递归程序：研究整个执行流程或采取“姑且相信”的态度（参见 6.8 节）。就这个示例而言，你完全可以采取姑且相信的态度。

用 selectionSort 对各个部分进行排序时，不必研究整个执行流程。可以假定 selectionSort 能够正确地运行，因为你之前调试过了。为将 mergeSort 变成递归的，你只是将一种排序算法替换成了另一种排序算法，因此没有理由采用不同的方式来研究程序。

准确地说，差不多是这样的，因为你可能需要确保基线条件没问题且它终将得以满足。除此之外，递归版本与非递归版本没有其他不同。