public class MergeSort implements IMutableSorter {
  @Override
  public void sort(int[] A) {
    //左闭右闭
    mergeSort(A, 0, A.length - 1);
  }
  private void mergeSort(int[] A, int left, int right) {
    if (left >= right) {
      return;
    }
    int mid = left + (right - left) / 2;
    mergeSort(A, left, mid);
    mergeSort(A, mid + 1, right);
    merge(A, left, mid, right);
  }
  private void merge(int[] A, int left, int mid, int right) {
    int[] L = Arrays.copyOfRange(A, left, mid + 1);
    int[] R = Arrays.copyOfRange(A, mid + 1, right + 1);
    int i = 0, j = 0;
    for (int k = left; k <= right; k++) {
      if (i == L.length) {
        A[k] = R[j++];
      } else if (j == R.length || L[i] <= R[j]) {
        A[k] = L[i++];
      } else {
        A[k] = R[j++];
      }
    }
  }
}

merge其实还有另外一种写法
看看能记住哪种吧

  private void merge(int[] A, int left, int mid, int right) {
    //预留一个多余的节点
    int[] L = Arrays.copyOfRange(A, left, mid + 2);
    int[] R = Arrays.copyOfRange(A, mid + 1, right + 2);
    L[L.length - 1] = Integer.MAX_VALUE;
    R[R.length - 1] = Integer.MAX_VALUE;
    int i = 0, j = 0;
    for (int k = left; k <= right; k++) {
      if (L[i] <= R[j]) {
        A[k] = L[i++];
      } else {
        A[k] = R[j++];
      }
    }
  }

148. 排序链表

可以理解为归并排序
对找到中间节点做了一点修改，这里的函数找到的是中间节点的前一个节点，方便断开链表。

class Solution {
    public ListNode sortList(ListNode head) {
        if(head==null||head.next==null) return head;
        ListNode midNode=findMidNode(head);
        ListNode rightHead=midNode.next;
        midNode.next=null;
        ListNode left=sortList(head);
        ListNode right=sortList(rightHead);
        return mergeTwoLists(left,right);
    }

    private ListNode findMidNode(ListNode head){
        if(head==null||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;
    }

    private ListNode mergeTwoLists(ListNode l1,ListNode l2){
        ListNode res=new ListNode();
        ListNode cur=res;
        while(l1!=null&&l2!=null){
            if(l1.val>l2.val){
                cur.next=l2;
                l2=l2.next;
            }else{
                cur.next=l1;
                l1=l1.next;
            }
            cur=cur.next;
        }
        cur.next=l1!=null?l1:l2;
        return res.next;
    }
}

剑指 Offer 51. 数组中的逆序对

class Solution {
    int count=0;

    public int reversePairs(int[] nums) {
        mergeSort(nums,0,nums.length-1);
        return count;
    }

    public void mergeSort(int[] nums, int l, int r){
        if(l>=r){
            return;
        }
        int mid=l+(r-l)/2;
        mergeSort(nums,l,mid);
        mergeSort(nums,mid+1,r);
        merge(nums,l,mid,r);
    }

    public void merge(int[] nums,int l,int mid,int r){
        int[] L=Arrays.copyOfRange(nums,l,mid+1);
        int[] R=Arrays.copyOfRange(nums,mid+1,r+1);
        int i=0,j=0;
        for(int k=l;k<=r;k++){
            if(i==L.length){
                nums[k]=R[j++];
            }else if(j==R.length||L[i]<=R[j]){
                nums[k]=L[i++];
            }else{
                nums[k]=R[j++];
                count+=L.length-i;
            }
        }
    }
}