有了这个代码模板，合并排序手到擒来

最后，不管是二叉树还是合并排序都要考虑一下边界：

二叉树的边界就是节点不能为空。

if (root === null) return null;

合并排序的边界就是：

• 当 b >= e，说明这个区间是一个空区间，没有必要再排序；
• 当 b + 1 === e，说明只有一个元素，也没有必要排序。

if (b > e || b + 1 >= e) {
  return 
}

小结

对于二叉树来说，代码相对比较简单。

function postOrder(root, array = []) {
  // 边界处理
  if (root === null) return null;
  // 第一步：划分子结构，二叉树在结构上已经划分了子结构 root.left、root.right 可以直接通过树的子节点拿
  // 第二步：获取子结构信息（递归的方式）
  postOrder(root.left, array);
  postOrder(root.right, array);
  // 第三步：整合子结构信息
  array.push(root.val)
}

对于二叉树来说，如何切分左右子数组？如何进行合并，合并时注意循环的条件，以及稳定排序的写法？都是在写算法时需要注意的。

接着我们利用刚才将的例子来看几个例子。

例1：排序链表

给你链表的头结点 head ，请将其按 升序 排列并返回 排序后的链表 。

这道题目就可以套用我们上面提到的模板。

第一步：划分子结构，对于链表来说划分子结构，也就是找到链表的中间节点。链表找中间节点也就是利用我上一篇文章中讲到的“快慢指针”。

let fast = head,
    slaw = head;

// 第一步：划分子结构，快慢指针，一个节点走一步，另外一个节点走两步，一快一慢
// 这里 tail 相当于上面数组中的 end，对于链表来说，end 也就是 null
while(fast !== tail) {
    slaw = slaw.next;
    fast = fast.next;
    if (fast && fast !== tail) {
        fast = fast.next;
    }
}
const mid = slaw;

第二步：获取子结构信息（递归的方式）。

// 第二步：获取子结构信息
const list1 = sort(head, mid);
const list2 = sort(mid, tail)

第三步：整合信息，有了两个子结构信息，也就需要将两个子结构信息合成一个，对于链表来说就是合并两个有序链表。这里合并的过程中，还可以用到到我上一篇文章说到的“链表第一板斧，假头”。

// 第三步：整合，合并两个有序链表
var merge = function(head1, head2) {
    const dummy = new ListNode();
    let tail = dummy;
    let list1 = head1;
    let list2 = head2;
    while(list1 && list2) {
        if (list1.val < list2.val) {
            tail.next = list1;
            tail = list1;
            list1 = list1.next;
        } else {
            tail.next = list2;
            tail = list2;
            list2 = list2.next;
        }
    }
    if (list1) {
        tail.next = list1;
    }
    if (list2) {
        tail.next = list2;
    }
    return dummy.next;
}

最后少不了临界条件的判断。

if (head === null) {
      return head;
  }
  if (head.next === tail) {
      head.next = null;
      return head;
  }

完整的代码如下：

var merge = function(head1, head2) {
    const dummy = new ListNode();
    let tail = dummy;
    let list1 = head1;
    let list2 = head2;
    while(list1 && list2) {
        if (list1.val < list2.val) {
            tail.next = list1;
            tail = list1;
            list1 = list1.next;
        } else {
            tail.next = list2;
            tail = list2;
            list2 = list2.next;
        }
    }
    if (list1) {
        tail.next = list1;
    }
    if (list2) {
        tail.next = list2;
    }
    return dummy.next;
}
function sort(head, tail) {
    if (head === null) {
        return head;
    }
    if (head.next === tail) {
        head.next = null;
        return head;
    }
    let fast = head,
        slaw = head;
    // 第一步：划分子结构，快慢指针，一个节点走一步，另外一个节点走两步，一快一慢
  // 这里 tail 相当于上面数组中的 end，对于链表来说，end 也就是 null
    while(fast !== tail) {
        slaw = slaw.next;
        fast = fast.next;
        if (fast && fast !== tail) {
            fast = fast.next;
        }
    }
    const mid = slaw;
    // 第二步：获取子结构信息
    const list1 = sort(head, mid);
    const list2 = sort(mid, tail)
    // 第三步：整合，合并两个有序链表
    return merge(list1, list2);

}
var sortList = function(head) {
    if (head === null || head.next === null) {
        return head;
    }
    return sort(head, null)
};

例2：寻找两个正序数组的中位数

给定两个大小分别为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出并返回这两个正序数组的 中位数 。

算法的时间复杂度应该为 O(log (m+n)) 。

这是一道来自百度的面试题。解法有很多，我们重点介绍基于合并模板的解法。

如果单纯的不考虑复杂度，通过合并排序，我们已经能够将两个有序的数组合并成一个有序的数组了，再取这个有序数组的中位数。

但是这样操作的话，时间复杂度就变成 O(N)，并且空间复杂度也是 O(N)。

如果在面试现场，面试官一定会问你，有没有更好的办法？所以我们应该有效地利用两个数组的有序性解决这道题。下面我会从简单的情况开始分析。

假设我们有一个一维有序数组，如果我们要拿第 9 小的数。（注：第 1 小就是最小的数。）只需要将前面 8 个数扔掉，然后排在前面的数就是第 9 小的数。

但是现在我们有多个有序数据，怎么办了？但是非常确认的是，我们如果想拿到第 9 小的数，一定需要丢 8 个数。

那么接下来，思考一下在两个数组 A，B 中如何扔掉这 8 个数？

图片

图片

所以总结一下，当我们需要丢弃 K 个元素的时候。k 是偶数的时候，我们只需要比较 A[k/2-1] 和 B[k/2-1] 的大小，谁小就扔掉对应的 [0...k/2-1] 这一段；k 是奇数的时候，我们只需要比较 A[k/2] 和 B[k/2] 的大小，谁小就扔掉对应的 [0...k/2] 这一段。不过由于整数在程序中的整除特性，我们可以将奇数和偶数的情况统一起来。需要扔掉 k 个数的时候，p = (k-1)/ 2，你只需要比较 A[p] 和 B[p] 的大小即可。如果 A[p] >= B[p]，那么就可以把 B[0....p] 这段都扔掉。

var findMedianSortedArrays = function(A, B) {
    let len = A.length + B.length;
    let alen = A.length, blen = B.length;
    let i = 0, j = 0;
    // 如果两个数组的总长度为0
    //那么不用再找了，肯定是没有中位数的，这里直接返回一个0
    if (len == 0) {
        return 0;
    }
    // 总长度为偶数的情况：
    // 如果有4个数，那么当扔掉1个数之后
    // 接下来需要合并的两个数排[2,3]就是中位数
    // 总长度为奇数的情况：
    // 比如如果有5个数，那么当合并掉2个数之后
    // 接下来的那个排[3]位的就是中位数。
    // 所以这里k表示：要扔掉的数的个数
    // 第一步：划分子结构
    let k = (len - 1) >> 1;
    // 第二步：找到子结构信息
    while (k > 0) {
        // 我们需要比较A[p]与B[p]
        // 只不过当数组的起始位置是i和j的时候。
        // 比较的元素就变成 A[i+p], B[j+p]
        let p = (k - 1) >> 1;
        // 这时直接比较A[i + p]和B[j+p]来决定谁可以被扔掉掉
        // 注意这里扔掉的时候，只需要前移p + 1即可。
        if (j + p >= blen || (i + p < alen && A[i + p] = blen || (i < alen && A[i] = blen || (i < alen && A[i] < B[j])) ? A[i] : B[j];
    return (front + back) / 2.0;
};