mergesort.java

Java 入门书的源码

//Copyright (c) 1998, Arthur Gittleman
//This example is provided WITHOUT ANY WARRANTY either expressed or implied.

/* Implements the recursive merge sort
 * algorithm to sort an array that the user
 * inputs on the command line.
 */

public class MergeSort {
  public static void mergeSort (int [] data, int left, int right) {
    if (left < right) {
      int middle = (left+right)/2;
      mergeSort(data,left,middle);
      mergeSort(data,middle+1,right);
      merge(data,left,middle,middle+1,right);
    }
  }
  public static void merge(int[] data, int l1, int r1, int l2, int r2) {
    int oldPosition = l1;
    int size = r2-l1+1;
    int [] temp = new int[size];
    int i = 0;  
    while (l1<=r1 && l2<=r2) {
      if (data[l1] <= data[l2]) 
        temp[i++] = data[l1++];
      else
        temp[i++] = data[l2++];
    }
    if (l1 > r1) 
      for (int j=l2; j<=r2; j++)
        temp[i++] = data[l2++];
    else
      for (int j=l1; j<=r1; j++)
        temp[i++] = data[l1++];
    System.arraycopy(temp,0,data,oldPosition,size);
  }
  public static void display(int [] anArray) {
    System.out.print("{");
    for (int i=0; i<anArray.length; i++) { 
      if (i!=0) System.out.print(",");
      System.out.print(anArray[i]);
    }
    System.out.println("}");
  }
  public static void main (String [] args) {
    int [] data = new int[args.length];
    for (int i=0; i < data.length; i++)
      data[i] = Integer.parseInt(args[i]);
    mergeSort(data,0,data.length-1);
    display(data);
  }
}