A和B是两个有序数组(假设为递增序列)，而且A的长度足以放下A和B中所有的元素， 写一个函数将数组B融入数组A，并使其有序。
最简单的方法是开一个大小可以容纳A和B的数组C，然后像归并排序中合并两个数组一样， 按照大小顺序把数组A和数组B的元素一一地放入数组C，然后再将数组C拷贝给A。 这种方法额外地使用了O(n)的空间，显然这是没有必要的开销。由于A的大小已经足够用了， 所以直接在A上直接操作即可。
可是如果我们思维定势地对比数组A和数组B，每次取小的元素放入数组A， 这样就会发现，要放入的位置上正放着有用的元素。处理起来就麻烦了。
相反，如果我们从A和B的尾部元素开始对比，每次取大的元素放在数组A的尾部， 这样一来，要放入的位置就不会出现上面的冲突问题。当对比结束时， 即可得到一个排好序的数组A。代码如下：
对比结束后，要检查数组B中是否还有元素，有的话要将它们拷贝到数组A。 我们并不需要检查数组A，因为如果数组A还有元素，说明while循环是因为数组B 中没有元素了才退出的。而A中的元素本来就是有序且就位于数组A中，所以不需要再管它。 如果A和B中的元素个数为n和m，则该算法的时间复杂度为O(n+m)。
让我们再加点限制条件，如果两个有序的序列并且没有额外的空间，那要怎么排序。 比如对于数组A，它的前半段和后半段分别有序，不使用额外的空间怎么使A整体有序。
首先，不可避免的我们还是要将两个有序部分中的元素拿出来对比。 我们先拿出前半段的第一个元素和后半段的第一个元素进行对比， 如果后半段的第一个元素要小，就将它们交换。由于这两个元素是各自序列的最小值， 这一对比就将整个数组A的最小值取出放在了正确的位置上。然后呢？ 交换到后半段的那个值怎么办？不理它，不太合适吧。我们可以通过两两对比， 把它移动到后半段的某个位置，使后半段保持有序。接下来呢？ 我们取出前半段的第2个元素(第1个元素已经放在它正确的位置上，不用理它了)， 还是和后半段的第1个元素对比，这一对比中较小的就会是整个数组中第2小的元素， 如果是后半段那个元素较小，则交换它们，然后仍然移动后半段使其保持有序。 这样不断进行下去，当把前半段的元素都遍历操作一遍，就会将小的元素都移动到前半段， 并且是有序的。而大的元素都在后半段且也是有序的。排序结束。
代码如下：