mergesort.java

《算法设计与分析》王晓东编著

import java.util.Scanner;
public class MergeSort {

	/**
	 * @param args
	 */
	public static void mergeSort(int[] array,int p1,int p2){
		if(p1>=p2) return;
		int mid = (p1+p2)/2;
		mergeSort(array,p1,mid);
		mergeSort(array,mid+1,p2);
		int[] a = new int[p2-p1+1];
		int q1 = p1;
		int q2 = mid+1;
		int i = 0;
		while(q1<=mid && q2<=p2){
			if(array[q1]<array[q2]) {
				a[i] = array[q1++];
			}
			else{
				a[i] = array[q2++];
			}
			i++;
		}
		while(q1 <= mid)
			a[i++] = array[q1++];
		while(q2 <= p2)
			a[i++] = array[q2++];
		for(i=0;i<p2-p1+1;i++){
			array[p1+i] = a[i];
		}
			
	}
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner in = new Scanner(System.in);
		System.out.print("Please input the length of the array:");
		int n = in.nextInt();
		int[] array = new int[n];
		for(int i=0;i<n;i++){
			System.out.print("array["+i+"] = ");
			array[i] = in.nextInt();
		}
		mergeSort(array,0,n-1);
		System.out.println("The result of mergeSort:");
		for(int i=0;i<n;i++){
			System.out.print(array[i]+"\t");
		}
	}

}