今天在leetcode上刷到一题链表排序的题，遇到排序题不能总用快排吧，换个口味，归并排序。如果数组项只有一项或者两项，排序是最简单的，只需比较大小交换一下位置即可。归并排序就是基于这个准则，不断的对数组进行二分，讲一个拥有n项的数组打散成n多个只有一项或者两项的数组，然后将这n多项的数组进行合并，最终合并起来的数组就是排好序的数组了。
步骤：
1.定义两个函数，将数组“打碎”的函数sort和负责将两个数组和并的函数merge
2.merge接收两个参数，即两个需要合并的数组，当然也负责比较大小，进行有序合并
3.sort负责将数组一分为二并排序，将这两个数组传入merge,怎么获取排好序的数组呢？只需要递归调用自身即可获得排好序的数组
代码如下：
var sort=function(arr){ if(arr.length<=1) return arr; let mid=parseInt(arr.length/2); // 递归调用自身，拆分的数组都是排好序的，最后传入merge合并处理 return merge(sort(arr.slice(0,mid)),sort(arr.slice(mid))); } // 将两个排好序的数组合并成一个顺序数组 var merge=function(left,right){ let res=[]; while(left.length>0 && right.length>0){ // 不断比较left和right数组的第一项，小的取出存入res left[0]<right[0]?res.push(left.shift()):res.push(right.shift()); } return res.concat(left,right); }
如果要使用归并排序一个链表，使用快慢指针获取链表中心点，leetcode地址：148. Sort List，代码如下：
// 归并排序 var sortList = function(head) { if(!head || !head.next) return head; let pre=head,slow=head,fast=head; while(fast && fast.next){ pre=slow; slow=slow.next; fast=fast.next.next; } pre.next=null; return merge(sortList(head),sortList(slow)); }; var merge=function(l1,l2){ let node=new ListNode(-1); let cur=node; while(l1 && l2){ if(l1.val<l2.val){ cur.next=l1; l1=l1.next; }else{ cur.next=l2; l2=l2.next; } cur=cur.next; } if(l1) cur.next=l1; if(l2) cur.next=l2; return node.next; }
原文：https://www.cnblogs.com/xingguozhiming/p/10306513.html