1.歸并排序的基本思想

將待排序序列R[0...n-1]看成是n個長度為1的有序序列瓶蝴，將相鄰的有序表成對歸并，得到n/2個長度為2的有序表租幕；將這些有序序列再次歸并舷手，得到n/4個長度為4的有序序列；如此反復(fù)進行下去劲绪，最后得到一個長度為n的有序序列男窟。

綜上可知：

歸并排序其實要做兩件事：

（1）“分解”——將序列每次折半劃分盆赤。

（2）“合并”——將劃分后的序列段兩兩合并后排序。

我們先來考慮第二步歉眷，如何合并牺六？

在每次合并過程中，都是對兩個有序的序列段進行合并汗捡，然后排序淑际。

這兩個有序序列段分別為 R[low, mid] 和 R[mid+1, high]。

先將他們合并到一個局部的暫存數(shù)組R2中扇住，帶合并完成后再將R2復(fù)制回R中春缕。

為了方便描述，我們稱 R[low, mid] 第一段艘蹋，R[mid+1, high] 為第二段锄贼。

每次從兩個段中取出一個記錄進行關(guān)鍵字的比較，將較小者放入R2中女阀。最后將各段中余下的部分直接復(fù)制到R2中宅荤。

經(jīng)過這樣的過程，R2已經(jīng)是一個有序的序列浸策，再將其復(fù)制回R中膘侮，一次合并排序就完成了。

package com.ustc.algorithm;

import java.util.Arrays;

/** 
* @author 王聰
* @version 創(chuàng)建時間：2017年2月24日 下午7:57:17 
* 類說明 
*/
public class MergeSort {
    /**
     * 歸并排序
     * 簡介:將兩個（或兩個以上）有序表合并成一個新的有序表 即把待排序序列分為若干個子序列的榛，每個子序列是有序的琼了。然后再把有序子序列合并為整體有序序列
     * 時間復(fù)雜度為O(nlogn)
     * 穩(wěn)定排序方式
     * @param nums 待排序數(shù)組
     * @return 輸出有序數(shù)組
     */
    public static int[] sort(int[] nums, int low, int high) {
        int mid = (low + high) / 2;
        while (low < high) {
            // 左邊
            sort(nums, low, mid);
            // 右邊
            sort(nums, mid + 1, high);
            // 左右歸并
            merge(nums, low, mid, high);
        }
        return nums;
    }

    public static void merge(int[] nums, int low, int mid, int high) {
        int[] temp = new int[high - low + 1];
        int i = low;// 左指針
        int j = mid + 1;// 右指針
        int k = 0;

        // 把較小的數(shù)先移到新數(shù)組中
        while (i <= mid && j <= high) {
            if (nums[i] < nums[j]) {
                temp[k++] = nums[i++];
            } else {
                temp[k++] = nums[j++];
            }
        }

        // 把左邊剩余的數(shù)移入數(shù)組
        while (i <= mid) {
            temp[k++] = nums[i++];
        }

        // 把右邊邊剩余的數(shù)移入數(shù)組
        while (j <= high) {
            temp[k++] = nums[j++];
        }

        // 把新數(shù)組中的數(shù)覆蓋nums數(shù)組
        for (int k2 = 0; k2 < temp.length; k2++) {
            nums[k2 + low] = temp[k2];
        }
    }

    
    // 歸并排序的實現(xiàn)
    public static void main(String[] args) {

        int[] nums = { 2, 7, 8, 3, 1, 6, 9, 0, 5, 4 };

        MergeSort.sort(nums, 0, nums.length-1);
        System.out.println(Arrays.toString(nums));
    }
}