java归并排序

package com.arithmetic;

import java.util.Random;

/**
 * 归并排序
 * 
	一个归并排序的例子:对一个随机点的链表进行排序
	分类				排序算法
	数据结构			数组
	最差时间复杂度	Θ(nlog n)
	最优时间复杂度	Θ(n)
	平均时间复杂度	Θ(nlog n)
	最差空间复杂度	Θ(n)
	最佳算法			有时是
 * 
 * @author xugang
 *
 */
public class Merge {
	//合并已排序的数组
	public static void merge( int[] arr , int low , int mid ,int high , int[] temp  ){ //int[] a , int[] b
		int first = low ;
		int first2 = mid+1 ;
		int i = 0 ;
		for(  ; first<=mid && first2<=high; i++ ){
			if( arr[first] < arr[first2] ){
				temp[i] = arr[first];
				first++;
			} else{
				temp[i] = arr[first2];
				first2++;
			}
		}
		while( first<=mid){
			temp[i] = arr[first];
			first++;i++;
		}
		while( first2<=high){
			temp[i] = arr[first2];
			first2++;i++;
		}
		
		for (int p = 0; p < i ; p++) {
			arr[low+p] = temp[p];
		}
	}
	
	//递归 
	public void mergeSort( int[] arr , int first , int last , int[] temp ){
		int mid = 0 ;
		if( first < last ){
			mid = (first+last)/2  ;
			mergeSort(arr, first, mid , temp);
			mergeSort(arr, mid+1, last , temp);
			merge(arr, first, mid, last , temp );
		}
	} 
	
	public static void main(String[] args) {
		Random random = new Random();
		int size = 100000 ;
		int[] r = new int[size];
		for (int i = 0; i < r.length; i++) {
			r[i] = Math.abs(random.nextInt())%10000000 ; 
		}
		Merge m = new Merge();
		int[] temp = new int[r.length];
		long l1 = System.currentTimeMillis();
		m.mergeSort(r, 0, r.length-1,temp);
		long l2 = System.currentTimeMillis();
		System.out.println( "消耗=" + (l2 - l1) ) ;
//		for (int i = 0; i < r.length; i++) {
//			System.out.println(r[i]);
//		}
	}
}