Merge Sort (合併排序法)

package sort;

public class MergeSortDemo {
 
 
 public static void main(String[] args) {
  int[] array = { 3, 3,2,1,0,4,5,1,4};
  array = mergeSort(array);
  for (int i = 0; i < array.length; i++) {
   System.out.print(array[i] + " ");
  }
 }

 public static int[] mergeSort(int[] list) {
  //if merely left 1 element return list;
  if (list.length <= 1) {
   return list;
  } else {
   int[] left;
   int[] right;
   int middle = list.length / 2;
   //declare left sub array;
   left = new int[middle]; 
   //declare right sub array;
   right = new int[list.length - middle];
   int j = 0;
   for (int i = 0; i < list.length; i++) {
    if (i < left.length) {
     //initialize left array
     left[i] = list[i];
    } else {
     //initialize right array
     right[j] = list[i];
     j++;
    }
   }
   //divide left array into small parts;
   left = mergeSort(left);
   //divide right array into small parts;
   right = mergeSort(right);
   //combine small parts of left and right 
   return merge(left, right);
  }
 }

 public static int[] merge(int[] left, int[] right) {
  int[] result = new int[left.length + right.length];
  int j = 0;
  while (left.length > 0 || right.length > 0) {
   //left and right array have elements.
   if (left.length > 0 && right.length > 0) {
    if (left[0] <= right[0]) {
     result[j] = left[0];
     left = shiftArray(left);
    } else {
     result[j] = right[0];
     right = shiftArray(right);
    }
    
   } else if (left.length > 0) {
    //left array has elements;
    result[j] = left[0];
    left = shiftArray(left);
   } else if (right.length > 0) {
    //right array has elements;
    result[j] = right[0];
    right = shiftArray(right);
   }
   j++;
  }
  return result;
 }

 private static int[] shiftArray(int[] i) {
  int[] result = new int[i.length - 1];
  for (int j = 0; j < result.length; j++) {
   result[j] = i[j+1];
  }
  return result;
 }
}

Reference Wiki