归并排序

• 分解成两个待排序的区间；
• 使用递归将两个子序列分别排好序；
• 申请空间，定义两个指针指向两个序列的起始位置，比较指针所指向的元素，选择相对小的元素放入合并空间。

统一格式：

if(right == left){
    return 0;
}

稳定性：

public void merge(int[] nums, int left, int mid, int right){
    int[] temp = new int[nums.length];
    System.arraycopy(nums, left, temp, left, right - left + 1);
    int i = left;
    int j = mid + 1;
    
    for(int k = 0; k <= right; k++){
        边界问题
        if(i == mid + 1){
            nums[k] = temp[j++];
        }else if(j == right + 1){
            nums[k] = temp[i++];
        }else if(temp[i] <= temp[j]){
            加上等号、遇到相同元素的时候优先放入左侧的数据，保证稳定性
            nums[k] = temp[i++];
        }else{
            nums[k] = temp[j++];
        }
    }
}

例题

例题：912. 排序数组

class Solution {
    public int[] sortArray(int[] nums) {
        // 归并排序
        if(nums.length == 0){
            return new int[]{};
        }
        reverse(nums, 0, nums.length - 1);
        return nums;
    }

    public void reverse(int[] nums, int left, int right){
        if(left == right){
            return;
        }
        // 排好序
        int mid = (right - left) / 2 + left;
        reverse(nums, left, mid);
        reverse(nums, mid + 1, right);

        // 合并
        merge(nums, left, mid, right);
    }

    public void merge(int[] nums, int left, int mid, int right){
        int[] temp = new int[nums.length];
        System.arraycopy(nums, left, temp, left, right - left + 1);
        int i = left;
        int j = mid + 1;

        for(int k = left; k <= right; k++){
            if(i == mid + 1){
                nums[k] = temp[j];
                j++;
            }else if(j == right + 1){
                nums[k] = temp[i];
                i++;
            }else if(temp[i] <= temp[j]){
                nums[k] = temp[i];
                i++;
            }else{
                nums[k] = temp[j];
                j++;
            }
        }
    }


}

例题：剑指 Offer II 077. 链表排序

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }

 归并
 */
class Solution {
    public ListNode sortList(ListNode head) {
        if(head == null || head.next == null){
            return head;
        }


        // 中间偏前的节点
        ListNode fast = head, slow = head;
        while(fast.next != null && fast.next.next != null){
            fast = fast.next.next;
            slow = slow.next;
        }

        ListNode mid = slow.next;
        // 将前面断开
        slow.next = null;

        ListNode l1 = sortList(head);
        ListNode l2 = sortList(mid);
        return merge(l1, l2);

    }

    // 合并
    public ListNode merge(ListNode l1, ListNode l2){
        ListNode head = new ListNode();
        ListNode node = head;

        while(l1 != null && l2 != null){
            if(l1.val < l2.val){
                node.next = l1;
                l1 = l1.next;
            }else{
                node.next = l2;
                l2 = l2.next;
            }

            node = node.next;
        }

        if(l1 != null){
            node.next = l1;
        }else if(l2 != null){
            node.next = l2;
        }

        return head.next;
    }
}

class Solution {
    public int reversePairs(int[] nums) {
        if(nums.length < 2){
            return 0;
        }

        return reversePairs(nums, 0, nums.length - 1, new int[nums.length]);
    }

    public int reversePairs(int[] nums, int left, int right, int[] temp) {
        if(left == right){
            return 0;
        }

                //排序
        int mid = (right - left) / 2 + left;
        int leftPairs = reversePairs(nums, left, mid, temp);
        int rightPairs = reversePairs(nums, mid + 1, right, temp);

        if(nums[mid] <= nums[mid + 1]){
            return leftPairs + rightPairs;
        }

                //合并两个子序列的过程
        int crossPairs = reversePairs(nums, left, mid, right, temp);
        return leftPairs + rightPairs + crossPairs;
    }

    public int reversePairs(int[] nums, int left, int mid, int right, int[] temp) {
        System.arraycopy(nums, left, temp, left, right - left + 1);
        int i = left;
        int j = mid + 1;
        int count = 0;

        for(int k = left; k <= right; k++){
            if(i == mid + 1){
                nums[k] = temp[j];
                j++;
            }else if(j == right + 1){
                nums[k] = temp[i];
                i++;
            }else if(temp[i] <= temp[j]){
                nums[k] = temp[i];
                i++;
            }else{
                nums[k] = temp[j];
                j++;
                count += mid - i + 1;
            }
        }
        
        return count;
    }
}