归并排序的优化方法有哪些？

归并排序 首先把数组分成一半，想办法把左右两边数组排序，之后呢再将它们归并起来，这就是归并排序的基本思想。 这样的话如果有N个元素，就会分成log(n)层，如果整个归并过程我们可以以O(n)时间复杂度解决的话，那么我们就设计成了一个 Nlog(n)级别的排序算法。 这个归并的过程需要O(n)的辅助空间，把两个已经排好序的数组合并成一个排序数组，整体呢需要三个索引在数组中追踪，其中蓝色的箭头表示最终在归并的过程中我们需要跟踪的位置，而俩个红色的箭头表示当前已经排好序的数组，分别指向当前要考虑的元素。 首先我们要看1和2谁先放在最终数组中，显然1比2小所以我们首先把1放在最终数组中，这样蓝色箭头就可以考虑下一元素应该放谁，与此同时，下面红色箭头1所在数组也可以考虑下一元素了，此时1这个元素就最终有序了，然后我们就可以考虑2和4谁放入最终数组，显然是2，以此类推。