消除递归的合并排序

思想：
因为递归法的归并排序实际上是将待排序的无序序列一分为二，直至分解到只剩下一个元素为止，然后不断合并二个排好序的子序列，按此思想可以写出消除递归的合并排序。这里使用的是分治策略。

/**
 * EliminateRecursionMergeSort.java
 * 
 * 非递归法实现合并排序.
 * 
 * @author Administrator
 *
 */
public class EliminateRecursionMergeSort {

	public static void eliminateRecursionMergeSort(int[] a) {
		int[] b = new int[a.length];
		
		int s = 1;	//有序序列的初始长度.
		
		while( s < a.length ) {
			
			Util.mergePass(a, b, s);	//合并数组a中大小为s的相邻元素到数组b.
			
			s*=2;
			
			Util.mergePass(b, a, s);	//合并数组b中大小为s的相邻元素到数组a.
			
			s*=2;
		}
		
	}
		
	/**
	 * @param args
	 */
	public static void main(String[] args) {
		if (args.length == 0) {
			System.out.println("请输入数字以空格隔开");
			System.exit(-1);
		}

		int[] a = new int[args.length];

		for (int i = 0; i < args.length; i++)

			a[i] = Integer.parseInt(args[i]);

		eliminateRecursionMergeSort(a);

		// 输出排序后的数组元素。
		for (int i = 0; i < a.length; i++)
			System.out.println(a[i]);
	}

}