归并排序是一种经典的排序算法，它通过分治的思想将待排序的数组划分为较小的子数组，然后递归地对这些子数组进行排序，最后将它们合并起来得到最终的有序数组。

在标准的归并排序算法中，合并操作是必不可少的，因为它负责将两个已排序的子数组合并成一个有序的数组。当我们面对一个已经有序的数组时，合并操作实际上是多余的。因为已经有序的数组不需要再进行合并，它们已经满足了排序的要求。

优化策略

因此，我们可以通过判断数组是否有序来跳过合并操作，从而提高算法的效率。在归并排序算法中，我们可以通过增加一个判断条件来实现这个优化。当我们在递归地对子数组进行排序时，我们可以在每次递归调用 merge() 方法之前，先检查子数组是否已经有序。如果是的话，我们可以直接返回，不再执行合并操作。这样一来，我们就可以避免不必要的合并操作，从而提高算法的性能。

实现

```java public static void mergeSort(int[] arr) { if (arr == null || arr.length <= 1) { return; } int mid = arr.length / 2; int[] left = Arrays.copyOfRange(arr, 0, mid); int[] right = Arrays.copyOfRange(arr, mid, arr.length); mergeSort(left); mergeSort(right); // 检查子数组是否已经有序 if (left[left.length - 1] <= right[0]) { System.arraycopy(left, 0, arr,

---

阿包说算法之《排序》

排序的方法有很多，本文主要介绍三种：冒泡排序，快速排序，归并排序。 在很多算法中，都会用到递归算法，因此递归不再单独讲。 算法思路 冒泡排序的思想是最符合常人思维的，比如一个数组：3,6,8,2,1。 首先选择第一个数3，然后从后面的数开始遍历，如果比数组 第一个数 小，就交换位置，否则继续： 比如，第一次比较3和6，3小，继续，3和8比，继续，3和2比，2小，就交换3和2的位置，数组变成2,6,8,3,1，这时数组 第一个数 是2，2和1比，1小，交换2和1的位置，变成1,6,8,3,2，此时第一轮遍历结束，可以看到一轮遍历可以把最小的数选出。 第二次从第2个数开始遍历，与后面的数比较，就是6依次和8,3比，跟3换位置，然后3和2比，又换位置，次轮结束后1,2,8,6,3。 继续下一轮，直到遍历结束。 可见第一次把最小的数放到第一位，第二次把第二小的数放到第二位，第N次把第N小的数放到第N位。 最终输出 说明：冒泡排序的时间复杂度为O(N^2)，冒泡排序写法可能不一定是跟上面的一样，但是思想是一致的 算法思路 快速排序法的思想是把数组的第一个数取出来作为分界点，让数组中小于他的数放在他左边，大于他的数放在他右边，比如 这组数字，选5为分界点，然后让34在5左边，97在5右边，变成 然后，对左右两部分34和97，分别继续重复上面的步骤，直到有序。 这里可以看出应该用到 递归 。 步骤如下，有一串数字3,6,8,2,7，首先把第一个数3取出来作为分界点，然后从最右边开始找小于3的数，7大于3跳过，继续看2，2小于3，就把2放到3的位置，2的位置空出来【2,6,8,,7】，再从左边开始，6大于3，就把6放到原来2的位置，6的位置空出来【2,,8,6,7】，再从右边8开始，8大于3跳过，下一个，是空了，则此轮结束，把3放到空位【2,3,8,6,7】。 然后对3左右两边的2和8,6,7分别按上面的步骤进行排序，就变成【2,3,6,7,8】 最终输出 说明：这种排序的方式是一种 分治 的思想，把大问题拆分成多个解法一样的小问题，这里是把大数组拆成前后2个解法一样的小数组，分成两部分的分治法又叫二分法，但是跟下面的二分法排序又不一样。 另外，快速排序代码会有多种不同的写法，但是思想是一致的，快速排序中有2个while，在极端情况下（比如数组是有序的，会遍历整个数组）的算法复杂度是O(N^2)，一般情况下是O(NlogN)，但实际上乱序的情况下，很快就能跳出while，所以被称为快速排序，此排序最实用，请读者牢记。 算法思路 归并排序思路是：将数组一分为二，再对分出来的2个子数组继续拆分，2分，拆分直到子数组只有一个数字，然后把所有的数字两两组合成有序小数组，最后合成一个完整数组，是典型的二分法，所以又叫做二分法排序 这里的思想是拆分后就变成有序数组（一个数字肯定有序），然后就是对有序数组的合并操作。 比如，拆分成836,52,继续拆分成8,3,6,5,2。 然后8和3组合成38, 38和6组合成368， 52组合成25,。 最后把368和25组合成。 最终输出 说明：归并排序用的是二分法，把数组分成2个子数组分别排序，实际上可以用三分法四分法，把数组分成3个子数组，4个子数组等都可以，读者可以自行思考如何使用三分法归并排序。 归并排序的时间复杂度是O(NlogN)

LeetCode题解：合并两个有序数组

给你两个按非递减排序的整数数组nums1和nums2，另外有两个整数m和n，分别表示nums1和nums2中的元素数目。 请你合并nums1和nums2，使合并后的数组同样按非递减顺序排列。 注意：最终，合并后数组不应由函数返回，而是存储在数组nums1中。为了应对这种情况，nums1的初始长度为m+n，其中前m个元素表示应合并的元素，后n个元素为0，应忽略，num2的长度为n。

输入： nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3 输出： [1,2,2,3,5,6] 解释： 需要合并 [1,2,3] 和 [2,5,6] 。 合并结果是 [1,2,2,3,5,6] ，其中斜体加粗标注的为 nums1 中的元素。

复杂度分析

比较两个数组的元素大小，每次将比较的较大值放置到当前的最大索引的位置。如果一方提前放置完毕，那么剩下的都放置另一方的元素。

复杂度分析