合并两个已经有序的部分
给定两个升序区域，可以比较它们当前最靠前的未输出元素，把较小者写到结果中，再向前推进相应位置。一边用尽后，把另一边余下内容接上。每个元素只需在这次合并中向结果移动一次，工作与两边总长度成正比。
这个过程要求两边原本已经有序。若较小元素藏在某边后面，只查看当前头部便不能保证下一项最小。归并排序正是先建立子区域的有序性，再把这个前提交给合并步骤，并非任意拆分后直接混合内容。
参考：[1]
递归拆分与自底向上合并
自顶向下的版本把数组分成两半，递归处理各半，再合并；长度至多一时直接返回。每层合并处理总共n个元素，均分产生对数级层数，因而在单位比较成本模型下得到O(n log n)的最坏时间。
自底向上的版本不必递归拆分，而从单个元素开始，先合并长度一的相邻区域，再处理长度二、四等区域。两种组织方式使用同一个有序合并原理；递归调用的写法本身不是归并排序成立的必要条件。
辅助空间、稳定性与跳过合并
常见数组版本先复制到辅助数组，再写回原数组，需要Θ(n)额外空间。若比较相等时优先取左侧原有项，就能保留同键记录的先后次序。稳定性依赖这条合并规则，而不是只要函数名叫归并就自然成立。
已经排好的输入，也可以通过检查两半边界来避免不必要的合并；基本版本未必带有这项优化。原地归并、链表归并及不同运行段策略还有各自实现条件，因此讨论时间、空间和最好情况时，应说明所用版本。