二路归并排序

package algrithm;

import java.util.Scanner;

public class Sort {

	public static void mergeSort(int a[], int l, int r) {
		if (l >= r)
			return;
		int mid=(l+r)/2;
		mergeSort(a, l, mid);
		mergeSort(a, mid+1, r);
		merge(a, l, mid, r);
		
	}
	//二路归并排序空间复杂度为O(n)，时间复杂度为O（nlgn）
	public static void merge(int a[], int l, int m,int r) {
		int tmp[]=new int[r-l+1];
		int i=l,j=m+1;
		int k=0;
		while(i<=m && j<=r) {
			if(a[i] <= a[j])
				tmp[k++]=a[i++];
			else
				tmp[k++]=a[j++];
		}
		while(i<=m)
			tmp[k++]=a[i++];
		while(j<=r)
			tmp[k++]=a[j++];
		for(i=l,k=0;i<=r;i++,k++){
			a[i]=tmp[k];
		}
	}

	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		int n=in.nextInt();
		int a[]=new int[n];
		for(int i=0;i<n;i++) {
			a[i]=in.nextInt();
		}
		mergeSort(a, 0, n-1);
		for(int i=0;i<n;i++) {
			System.err.println(a[i]);
		}
	}

}