歸并排序（Merge）是將兩個（或兩個以上）有序表合并成一個新的有序表，即把待排序序列分為若干個子序列，每個子序列是有序的。然后再把有序子序列合并為整體有序序列。

歸并排序是建立在歸并操作上的一種有效的排序算法。該算法是采用分治法（Divide and Conquer）的一個非常典型的應(yīng)用。 將已有序的子序列合并，得到完全有序的序列；即先使每個子序列有序，再使子序列段間有序。若將兩個有序表合并成一個有序表，稱為2-路歸并。

歸并排序算法穩(wěn)定，數(shù)組需要O(n)的額外空間，鏈表需要O(log(n))的額外空間，時間復(fù)雜度為O(nlog(n))，算法不是自適應(yīng)的，不需要對數(shù)據(jù)的隨機讀取。

工作原理：

1、申請空間，使其大小為兩個已經(jīng)排序序列之和，該空間用來存放合并后的序列

2、設(shè)定兩個指針，最初位置分別為兩個已經(jīng)排序序列的起始位置

3、比較兩個指針所指向的元素，選擇相對小的元素放入到合并空間，并移動指針到下一位置

4、重復(fù)步驟3直到某一指針達到序列尾

5、將另一序列剩下的所有元素直接復(fù)制到合并序列尾

用一張圖來展示:

package arithmetic;import java.util.Arrays;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;          if (low < high) {          	System.out.PRintln(mid+":"+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));      }  }個人覺得還是快速排序好一點.....這個歸并排序感覺有點.....可能是不太理解吧.