Merge Sort - 归并排序

Java

  2.     public static void main(String[] args) {
  3.         int unsortedArray[] = new int[]{6, 5, 3, 1, 8, 7, 2, 4};
  4.         mergeSort(unsortedArray);
  5.         System.out.println("After sort: ");
  6.         for (int item : unsortedArray) {
  7.             System.out.print(item + " ");
  8.         }
  9.     }
  11.     private static void merge(int[] array, int low, int mid, int high) {
  12.         int[] helper = new int[array.length];
  13.         // copy array to helper
  14.         for (int k = low; k <= high; k++) {
  15.             helper[k] = array[k];
  16.         // merge array[low...mid] and array[mid + 1...high]
  17.         int i = low, j = mid + 1;
  19.             // k means current location
  20.             if (i > mid) {
  21.             // no item in left part
  22.                 array[k] = helper[j];
  23.                 j++;
  24.             } else if (j > high) {
  25.             // no item in right part
  26.                 array[k] = helper[i];
  27.                 i++;
  28.             } else if (helper[i] > helper[j]) {
  29.             // get smaller item in the right side
  30.                 array[k] = helper[j];
  31.                 j++;
  32.             } else {
  33.             // get smaller item in the left side
  34.                 array[k] = helper[i];
  36.         }
  37.     }
  39.     public static void sort(int[] array, int low, int high) {
  40.         if (high <= low) return;
  41.         int mid = low + (high - low) / 2;
  42.         sort(array, low, mid);
  43.         sort(array, mid + 1, high);
  44.         merge(array, low, mid, high);
  45.         for (int item : array) {
  46.             System.out.print(item + " ");
  47.         }
  48.         System.out.println();
  49.     }
  51.     public static void mergeSort(int[] array) {
  52.         sort(array, 0, array.length - 1);

Reference

  • - Robert Sedgewick 的大作，非常清晰。