マージソート [ALDS1_5_B : Merge Sort]

マージソート | アルゴリズムとデータ構造 | Aizu Online Judge

AIZU ONLINE JUDGEの問題です。

一概にマージソートといっても、さまざまな実装方法があるようで、それで迷ってしまって実装するのにやたらと時間がかかってしまった。

僕が今回用いた実装方法は再帰で、実装するにあたっては以下のページをおおいに参考にしました。
マージソート - やさしいデスマーチ

package Blog;

import static java.lang.System.*;
import java.util.*;

public class Blog {
	static Scanner sc = new Scanner(System.in);
	static List<Integer> list = new ArrayList<>();
	static int num = 0;

	
	public static void main(String[] args) {
		int n = sc.nextInt();
		for (int i=0; i<n; i++) list.add(sc.nextInt());

		mergeSort(list);

		for (int i=0; i<list.size(); i++) out.print((i==0?"":" ")+list.get(i)); out.println();
		out.println(num);
	}

	
	static void mergeSort(List<Integer> list) {
		int size = list.size();

		//listの大きさが1なら再帰終了
		if (size == 1) return;

		//1でないなら分割
		ArrayList<Integer> L = new ArrayList<>(), R = new ArrayList<>();
		int M = size/2;

			//分割処理、左側を作成
			for (int i=0; i<M; i++) L.add(list.get(i));
			//分割処理、右側を作成
			for (int i=M; i<size; i++) R.add(list.get(i));

			
		//再帰
		mergeSort(L); mergeSort(R);

		//マージ処理
		list.clear();
		int indexL = 0, indexR = 0;
		while (indexL<L.size() || indexR<R.size()) {
			if (indexL == L.size()) {
				list.add(R.get(indexR)); indexR++; num++;
			}
			else if (indexR == R.size()) {
				list.add(L.get(indexL)); indexL++; num++;
			}
			else {
				int tempL = L.get(indexL);
				int tempR = R.get(indexR);
				if (tempL <= tempR) {
					list.add(tempL); indexL++;
				}
				else {
					list.add(tempR); indexR++;
				}
				num++;
			}
		}
	}
}

「//再帰」の部分を通過した時点で、リストLとリストRはそれぞれ少なくとも1つ以上の要素を持っていることになる。

次にこの二つのリストをマージ（結合）していくことになるのだが、この結合の処理が少し難しい。

二つのリストのそれぞれ先頭の要素を比較して、小さいほうから結合結果用リストに詰めていく。やることはこれだけなのだが、今回扱っているリストは連結リストではないので、それぞれ添え字を用意してやる必要がある。

参考にしたページではループを三回使っていたが、劣化コピーにはなりたくなかったので、何とか工夫して1ループに抑えてみた。

ループの処理の流れとしては、

＜継続条件：LもしくはRに要素が残っている＞
①Lに要素が残っていないなら、Rの先頭の要素を詰める
②Rに要素が残っていないなら、Lの先頭の要素を詰める
③上のどちらでもない（LにもRにも要素が残っている）なら、それぞれの先頭の要素を比較して、小さいほうを詰める

といった具合。

連結リストなら添え字を使う必要がなく、実装が多少は楽になると思う。その代わり、分割処理のほうが大変になると思われる。マージソートについて調べていて、マージソートは連結リストでこそ活躍する、とか何とか書いてある記事も見かけたので、今度時間があればマージソートと連結リストの関係について調べてみたい。

追記：番兵を使えばループ内処理をもっとスマートに書けた可能性アリ

ところで、このソースコードをそのままAIZU ONLINE JUDGEのページで提出するとTLEになる。これは、以前yukicoderの問題を解いていたときにも発生したのだが、Javaはどうもコンソール出力処理が遅いようで、要素数何十万という配列を順にコンソール出力していくと大抵TLEになってしまう。これを解決するには、StringBuilderで出力を文字列1つにまとめてから、出力する必要がある。