带你读《图解算法小抄》十四、排序（6）https://developer.aliyun.com/article/1348144?groupCode=tech_library
1）原理
归并排序的基本思想是将待排序的序列不断划分为两个子序列，直到每个子序列只剩下一个元素，然后再将这些子序列两两合并，直到最终得到有序的序列。具体的排序流程如下：
- 步骤1：将待排序序列分成两个子序列，分别进行递归排序；
- 步骤2：将两个已排序的子序列合并成一个有序序列。
function mergeSort(arr) { if (arr.length <= 1) { return arr; } const mid = Math.floor(arr.length / 2); const left = mergeSort(arr.slice(0, mid)); // 递归排序左半部分 const right = mergeSort(arr.slice(mid)); // 递归排序右半部分 return merge(left, right); // 合并左右两个有序子序列} function merge(left, right) { let i = 0; // 左半部分指针 let j = 0; // 右半部分指针 const merged = []; while (i < left.length && j < right.length) { if (left[i] < right[j]) { merged.push(left[i]); // 将较小值放入合并数组 i++; } else { merged.push(right[j]); // 将较小值放入合并数组 j++; } } // 将剩余的元素放入合并数组 return merged.concat(left.slice(i)).concat(right.slice(j)); }
2）优化手段：
尽管归并排序已经是一种高效的排序算法，但我们可以通过一些优化手段进一步提高其性能。下面介绍几种常见的优化策略：
插入排序优化：
对于小规模的子序列，插入排序的时间复杂度较低，因此可以在归并排序的过程中使用插入排序来提高性能。具体做法是，在划分到一定规模后，将子序列采用插入排序算法进行排序。
优化合并过程：
在合并两个有序子序列时，如果发现左边子序列的最大元素小于等于右边子序列的最小元素，那么说明整个序列已经有序，可以直接跳过合并操作，节省时间。
带你读《图解算法小抄》十四、排序（8）https://developer.aliyun.com/article/1348142?groupCode=tech_library
