归并排序

package sort;

import java.util.Arrays;

public class MergeSort {

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		int[] theArray = {1,9,5,4,7,2,3,8};
		mergesort(theArray, 0, theArray.length - 1);
		System.out.println(Arrays.toString(theArray));
	}
	public static void mergesort(int[] theArray, int first, int last){
		if(first < last) {
			int mid = (first + last) /2;
			mergesort(theArray, first, mid);
			mergesort(theArray, mid+1, last);
			merge(theArray, first, mid, last);
		}
	}
	private static void merge(int[] theArray, int first, int mid, int last){
		int maxSize = theArray.length;
		int[] tempArray = new int[maxSize];
		int first1 = first;
		int last1 = mid;
		int first2 = mid+1;
		int last2 = last;
		int index = first1;
		while((first1<=last1) && (first2<=last2)){
			if(theArray[first1]- theArray[first2] < 0) {
				tempArray[index] = theArray[first1];
				first1++;
			} else {
				tempArray[index] = theArray[first2];
				first2++;
			}
			index++;
		}
		while(first1 <= last1){
			tempArray[index] = theArray[first1];
			first1++;
			index++;
		}
		while(first2<= last2){
			tempArray[index] = theArray[first2];
			first2++;
			index++;
		}
		for(index = first; index <= last; ++index){
			theArray[index] = tempArray[index];
		}
	}
}