归并排序的主要思想是“分而治之”，可以达到O(nlogn)的时间复杂度。下图引自敬爱的邓俊辉老师和尹霞老师数据结构课程上的课件：
Paste_Image.png
从右边的例子可以看出，归并排序的步骤分为两步，首先对无序向量进行递归的分解，直到每个分组仅剩下一个元素，一个元素肯定是有序的；然后对分解的结果逐步进行有序归并。整个算法思路很清晰。我尝试实现了数组的归并排序以及链表的归并排序，贴出代码：
数组的归并排序
/*
数组的归并排序
@low： 归并排序分解数组过程中的低位；
@high： 归并排序分解数组过程中的高位；
@nums： 待排序数组
@result：存储排序结果的数组
*/
public void mergeSortForArrays(int low, int high, int[] nums, int[] result){
// 首先，递归分解数组，直到数组的元组只有一个
if(low < high){
int middle = (high + low) >> 1; // middle = (low + high) / 2
mergeSortForArrays(low , middle , nums , result); //左边归并排序，使得左子序列有序，注意这里nums[middle]可取
mergeSortForArrays(middle + 1, high , nums , result); //右边归并排序，使得右子序列有序
// 然后，从少到多进行归并
mergeForArrys(low , middle , high , nums , result);
}
}
/*
有序数组的归并算法
@low： 分解数组过程中的低位；
@middle：分解数组过程中左边与右边两个数组的分界点；
@high： 分解数组过程中的高位；
@nums： 原待排序数组
@result：存储归并排序结果的数组，最后需要更新到nums数组中。
其实这里可以不需要result参数，每次在merge的时候新开一个数组即可。但是这样会浪费空间
*/
public void mergeForArrys(int low , int middle , int high, int[] nums, int[] result){
System.out.println("merge" + low + " " + middle + " " + high);
int leftPosi = low; // 左序列的指针
int rightPosi = middle + 1; // 右序列的指针
int resultPosi = 0; // 结果数组维护的指针
// 归并：对于两个数组，分别从第一位开始比较其大小，将小的数存入result中，并将result与小的数所在数组的位置指针++
while(leftPosi <= middle && rightPosi <= high){
if(nums[leftPosi] < nums[rightPosi]){
result[resultPosi++] = nums[leftPosi++];
}
else{
result[resultPosi++] = nums[rightPosi++];
}
}
// 一个数组不能移动后，将另外一个数组的剩余值填充进result
// 注意这里下面的两个while只有一个会成立
while(leftPosi <= middle) {
result[resultPosi++] = nums[leftPosi++];
}
while(rightPosi <= high){
result[resultPosi++] = nums[rightPosi++];
}
// 将排序后的值写回原数组
for(int i = 0;i < resultPosi;i++){
nums[low + i] = result[i];
}
}
链表的归并排序
/*
链表的归并排序
@head： 待排序链表头指针；
注意这里没有链表长度，用之前解leadCode：删除链表倒数第n个节点的思路，用两个快、慢指针找链表的一半
快指针需要先走len/2步，再和慢指针同步才能一起到结尾。如果让快、慢指针一起从头出发，则快指针需要一次移动两格
*/
public ListNode mergeSortForList(ListNode head){
// 为空或为单个，不用排序直接返回
if(head == null || head.next == null)
return head;
else{
ListNode fast = head.next;
ListNode slow = head;
// fast一次走两步，slow一次走一步
// fast必须从header.next开始，否则无法处理两个节点的情况
// 最后从slow.next处断开成两个链表
while(fast.next != null && fast.next.next != null){
fast = fast.next.next;
slow = slow.next;
}
// leftHead记录左边链表
ListNode leftHead = head;
// rightHead记录右边链表
ListNode rightHead = slow.next;
// 断开生成左边链表
slow.next = null;
// 继续进行递归拆分
leftHead = mergeSortForList(head);
rightHead = mergeSortForList(rightHead);
// 对新链表进行归并
return mergeForList(leftHead , rightHead);
}
}
/*
有序链表的归并算法
@leftHead： 拆分后左链表头指针；
@rightHead：拆分后右链表头指针；
初始两个链表指针leftHead和rightHead都在头部。比较其对应的val值，将值小的接入新的链表，同时移动链表指针
一个有序链表遍历完成后，需要将另一个链表剩下的元素接入新的链表
*/
public ListNode mergeForList(ListNode leftHead , ListNode rightHead){
// 存储归并后新的有序链表，最后返回newHead.next
ListNode newHead = new ListNode(-1);
ListNode tempHead = newHead;
// 比较val大小，移动链表并更新保存结果的有序链表
while(leftHead != null && rightHead != null){
if(leftHead.val < rightHead.val){
tempHead.next = new ListNode(leftHead.val);
leftHead = leftHead.next;
tempHead = tempHead.next;
}
else{
tempHead.next = new ListNode(rightHead.val);
rightHead = rightHead.next;
tempHead = tempHead.next;
}
}
// 将未遍历完的链表接入
if(leftHead == null)
tempHead.next = rightHead;
else
tempHead.next = leftHead;
// 返回归并后的有序链表
return newHead.next;
}
