归并排序的原理是分治算法。 如图，可以看到有两部分，一为分，一为治（合并）。这样有一个优点，与不稳定的快速排序相比，归并排序极为稳定。
import org.junit.Test; public class test { //两路归并算法，两个排好序的子序列合并为一个子序列 public void merge(int []a,int left,int mid,int right){ int []tmp=new int[a.length];//辅助数组 int p1=left,p2=mid+1,k=left;//p1、p2是检测指针，k是存放指针 while(p1<=mid && p2<=right){ if(a[p1]<=a[p2]) tmp[k++]=a[p1++]; else tmp[k++]=a[p2++]; } while(p1<=mid) tmp[k++]=a[p1++];//如果第一个序列未检测完，直接将后面所有元素加到合并的序列中 while(p2<=right) tmp[k++]=a[p2++];//同上 //复制回原素组 for (int i = left; i <=right; i++) a[i]=tmp[i]; } public void mergeSort(int [] a,int start,int end){ if(start<end){//当子序列中只有一个元素时结束递归 int mid=(start+end)/2;//划分子序列 mergeSort(a, start, mid);//对左侧子序列进行递归排序 mergeSort(a, mid+1, end);//对右侧子序列进行递归排序 merge(a, start, mid, end);//合并 } } @Test public void test(){ int[] a = { 49, 38, 65, 97, 76, 13, 27, 50 }; mergeSort(a, 0, a.length-1); System.out.println("排好序的数组："); for (int e : a) System.out.print(e+" "); } }难点就在于merge这个函数了，就是个合并两个数组的过程。
用到归并排序的力扣：排序链表
public ListNode sortList(ListNode head) { // 1、递归结束条件 if (head == null || head.next == null) { return head; } // 2、找到链表中间节点并断开链表 & 递归下探 ListNode midNode = middleNode(head); ListNode rightHead = midNode.next; midNode.next = null; ListNode left = sortList(head); ListNode right = sortList(rightHead); // 3、当前层业务操作（合并有序链表） return mergeTwoLists(left, right); } // 找到链表中间节点（876. 链表的中间结点） private ListNode middleNode(ListNode head) { if (head.next == null) { return head; } ListNode slow = head; ListNode fast = head.next.next; while (fast != null && fast.next != null) { slow = slow.next; fast = fast.next.next; } return slow; } // 合并两个有序链表（21. 合并两个有序链表） private ListNode mergeTwoLists(ListNode l1, ListNode l2) { ListNode sentry = new ListNode(-1); ListNode curr = sentry; while(l1 != null && l2 != null) { if(l1.val < l2.val) { curr.next = l1; l1 = l1.next; } else { curr.next = l2; l2 = l2.next; } curr = curr.next; } curr.next = l1 != null ? l1 : l2; return sentry.next; }总结：归并排序就是分割和合并的过程，链表的分割由于有引用变量，需要将中间结点的next为null。数组则不需要。
