将有序数组 归并排序 最多与最少比较次数

起一个记录性的作用。

设有两个有序数组 arr1 与 arr2，数组长度分别为 m 与 n， 要合并成一个长度位 m+n 的有序数组 arr3.

最差情况下：比较次数为 m+n-1

此时，将数组 arr1 与数组 arr2 中的元素两两比较，将值小的放进数组 arr3， 直到数组 arr3 填满为止。

因为 arr3 有 m+n 个空位，每次两两比较就放进去一个数，而最后一个剩下的元素可以不用比较直接放进去，所以一共两两比较了 m+n-1 次。

最好情况下：比较次数为 min{m, n}

有个疑问： 若一个数组为 1， 2，3 ； 另一个数组为 4, 5, 6, 7； 则直接将后一个数组最小的与前一个数组最大的比较，仅需一次比较就行了

一定要注意，这是简单归并排序，必须从第一个元素比。

因此，最好情况下，至少需要两两比较一个数组的长度，比较次数为 min{m,n}

例题：