「Javaデータ構造とアルゴリズム」学習ノート(5)-再帰集計ソート

各ノートには、本のAppletデモプログラムが添付されており、アルゴリズムが読めないものがあり、Appletのダウンロードで実行(htmlファイルを直接開くだけ)でき、アルゴリズムの一歩一歩を簡単に見ることができます.
メソッド呼び出し自体が,構成される.
再帰呼び出しです.通常、再帰には終了条件があります.そうしないと、プログラムは実行を停止できません.
集計ソート
集計ソートの原理(昇順ソート)は、2つの整列配列を1つの整列配列に結合し、2つの配列を比較することです.
第1項、
配列aの第1項がより大きい
配列bの第1項は、
配列bの第1項は、新しい配列にコピーされる.次に比較
配列aの第1項と
配列bの2番目の項目は、さらに小さいものを置く
新しい配列の2番目の位置で...マージが完了するまで.
再帰的なプロセスは,配列を分割し続けるプロセスであり,元の配列を分割できなくなるまで(長さが1)分割し続け,戻り,マージを開始する.
コードは次のとおりです.

	@SuppressWarnings("unchecked")
	public static <T extends Comparable<? super T>> void mergeSort(T[] array){
		T[] workspace = (T[])new Comparable[array.length];
		recallMergeSort(array, workspace, 0, array.length - 1);
	}
	
	private static <T extends Comparable<? super T>> void recallMergeSort
	(T[] array, T[] workspace, int lowerBound, int upperBound){
		if(upperBound == lowerBound){
			return;
		}else{
			int midIndex = (upperBound + lowerBound) / 2;
			recallMergeSort(array, workspace, lowerBound, midIndex);
			recallMergeSort(array, workspace, midIndex + 1, upperBound);
			merge(array, workspace, lowerBound, midIndex + 1, upperBound);
		}
	}
	
	private static <T extends Comparable<? super T>> void merge
	(T[] array, T[] workspace, int lowerIndex, int higherIndex, int upperBound){
		int i = 0;
		int midIndex = higherIndex - 1;
		int lowerBound = lowerIndex;
		while(lowerIndex <= midIndex && higherIndex <= upperBound){
			if(array[lowerIndex].compareTo(array[higherIndex]) < 0)
				workspace[i++] = array[lowerIndex++];
			else
				workspace[i++] = array[higherIndex++];
		}
		
		while(lowerIndex <= midIndex)
			workspace[i++] = array[lowerIndex++];
		
		while(higherIndex <= upperBound)
			workspace[i++] = array[higherIndex++];
		
		for(i=lowerBound; i<=upperBound; i++)
			array[i] = workspace[i - lowerBound];
	}

集計ソートの時間的複雑さはO(N*logN)であり,表挿入ソート法よりもはるかに速いが,必要である.
メモリ容量の1倍以上.長さ1万の配列を並べ替えると、時間はほとんど計算されません(ほとんど0です).配列を10倍に拡大したので、ランダムな配列を並べ替えるのに0.094秒、逆順序の並べ替えに0.11秒かかりました.