归并排序
思想
自顶向下划分
序列 [l, r] 被逐步二分为更小的序列 [l, m] 、[m+1, r]
自底向上归并
划分的最小有序序列为元素本身，子序列之间两两归并，归并成为新的有序序列之后再次两两合并，直到调和成为完整的有序序列
其中的合并操作为 合并两个有序序列：从两个有序序列逐一取值，按大小次序依次插入新的序列，可合并为一个新的有序序列。新序列若取原序列本身，可能会覆盖序列原值导致错误，需要一个 辅助序列aux 来保存合并结果
性能分析
时间复杂度 O(nlogn)
空间复杂度 O(n)
实现与优化
递归实现数组排序
子递归结果存入aux，父调用时基于aux的副本进行合并，即在合并前复制
class Solution { public int[] sortArray(int[] nums) { int[] aux = new int[nums.length]; mergeSort(nums, 0, nums.length - 1, aux); return aux; } public void mergeSort(int[] nums, int i, int j, int[] aux) { // 递归边界：不合法返回 if (i > j) return; // 递归边界：最小子序列是元素本身，合并入新序列aux if (i == j) { aux[i] = nums[i]; return; } // 自顶向下划分子序列，递归返回时两部分的aux已经分别有序 int m = i + ((j - i) >> 1); mergeSort(nums, i, m, aux); mergeSort(nums, m + 1, j, aux); // 后续归并基于分别有序的子序列，原地归并会覆盖原值，将部分有序结果复制回nums for (int k = i; k <= j; k++) { nums[k] = aux[k]; } // 基于nums中的两有序序列[l, m] 、[m+1, r]合并到aux中，合并时考虑指针到头情况 int s = i, f = m + 1, id = i; while (s <= m || f <= j) { if (s > m) aux[id++] = nums[f++]; else if (f > j) aux[id++] = nums[s++]; else if (nums[s] <= nums[f]) aux[id++] = nums[s++]; else aux[id++] = nums[f++]; } } }
优化递归数组排序
优化点1：避免不必要的合并，两有序序列本身已经组成新的有序序列时，省去合并
优化点2：合并递归边界减少复制，单个元素自成序不再处理，意味着保存两个有序序列的是nums，需要始终将合并结果存入nums。合并操作基于nums输出到辅助数组aux后需要复制回到nums
class Solution { public int[] sortArray(int[] nums) { int[] aux = new int[nums.length]; mergeSort(nums, 0, nums.length - 1, aux); return nums; } public void mergeSort(int[] nums, int i, int j, int[] aux) { // 递归边界，i > j不合法，i = j时nums[i]自成序 if(i >= j) return; // 子递归划分和归并，执行完后左右部分各自有序 int m = i + ((j - i) >> 1); mergeSort(nums, i, m, aux); mergeSort(nums, m + 1, j, aux); // 左右部分在本轮合并前已有序，剪枝 if(nums[m] < nums[m+1]) return; // 基于有序的nums进行归并 int s = i, f = m + 1, id = i; while(s <= m || f <= j) { if(s > m) aux[id++] = nums[f++]; else if(f > j) aux[id++] = nums[s++]; else if(nums[s] > nums[f]) aux[id++] = nums[f++]; else aux[id++] = nums[s++]; } // 恢复nums的有序性，供下轮aux合并使用 for(int k = i; k <= j; k++) { nums[k] = aux[k]; } } }
递归实现链表排序
自顶向下划分时需要找到链表中点并切分为两个链表，清空第一个表尾next域
在合并阶段可使用 虚拟头节点 ，避免复杂的边界条件判断
合并时两个链表已经有序，其中一个链表到达尽头，直接将另一条链表接到表尾即可
class RecursiveMergeSort { public ListNode sortList(ListNode head) { return mergeSort(head); } public ListNode mergeSort(ListNode head) { // 递归边界，空节点或单个节点自有序 if (head == null || head.next == null) { return head; } // 得到链表中点后切开两个链表 ListNode fast = head, mid = head, clr = null; while (fast != null && fast.next != null) { fast = fast.next.next; clr = mid; mid = mid.next; } clr.next = null; // 自顶向下划分得到两个有序序列 head = mergeSort(head); mid = mergeSort(mid); // 自底向上归并 ListNode dum = new ListNode(Integer.MIN_VALUE, null); ListNode cur = dum; while (head != null && mid != null) { if (head.val < mid.val) { cur.next = head; head = head.next; } else { cur.next = mid; mid = mid.next; } cur = cur.next; } // 处理一个指针到头的情况，此时两链表均有序 if (head == null) cur.next = mid; if (mid == null) cur.next = head; // 返回合并后链表的新头节点 return dum.next; } }
迭代
偶数对可以两两合并，四四合并，八八合并
偶数对合并过程示例
01 23 45 67
0123 4567
01234567
奇数对元素的合并处理过程需要特殊处理
奇数对合并过程示例
01 23 45 6
0123 456
0123456
奇数对合并过程示例
01 23 4
0123 4
01234
奇数对合并过程示例
01 23 45
0123 45
012345
class MergeSortIteration { public int[] sortArray(int[] nums) { int[] aux = new int[nums.length]; // sz扩到何时停止？由于奇数的特殊性不能使sz在N/2时停止，应扩到和数组同长度时，同长度为最后一轮已成序无需归并 for (int sz = 1; sz < nums.length; sz <<= 1) { // lo移到何时停止？最后部分小于sz时lo + sz < nums.length for (int lo = 0; lo + sz < nums.length; lo += (sz << 1)) { int s = lo, st = lo + sz; // 不足sz的后半部分末尾设定为num.length int f = lo + sz, ft = Math.min(lo + (sz << 1), nums.length); int id = lo; // 合并 [s, st) [f, ft) while (s < st && f < ft) { if (nums[s] < nums[f]) aux[id++] = nums[s++]; else aux[id++] = nums[f++]; } // 以nums为基础归并到aux中 if (s >= st) while (f < ft) aux[id++] = nums[f++]; if (f >= ft) while (s < st) aux[id++] = nums[s++]; // 复制回nums for (int k = lo; k < ft; k++) nums[k] = aux[k]; } } return nums; } }
参考资料
Sedgewick R, Wayne K. Algorithms, Fourth Edition[M]. 4. 人民邮电出版社, 2012.