Javaで学ぶアルゴリズム -マージソート

# マージソート

> マージソートは、ソートのアルゴリズムで、既に整列してある複数個の列を1個の列にマージする際に、小さいものから先に新しい列に並べれば、新しい列も整列されている、というボトムアップの分割統治法による。大きい列を多数の列に分割し、そのそれぞれをマージする作業は並列化できる。

https://ja.wikipedia.org/wiki/%E3%83%9E%E3%83%BC%E3%82%B8%E3%82%BD%E3%83%BC%E3%83%88

# 実行環境

- JUnit 5
- Java 8

# テストコード

```java:MergeSortTest.java
import static org.hamcrest.CoreMatchers.is;
import static org.hamcrest.MatcherAssert.assertThat;

import org.junit.jupiter.api.DisplayName;
import org.junit.jupiter.api.Test;

public class MergeSortTest {

	@DisplayName("配列を渡すとソートされた配列が返ること")
	@Test
	void testStraightExchange() {
		int[] array = { 5, 12, 7, 0, 1, 14, 6, 9, 8, 3, 2, 11, 4, 13, 10 };
		int[] expected = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14 };

		int[] actual = MergeSort.mergeSortWrapper(array);
		assertThat(actual, is(expected));
	}

	@DisplayName("要素が1つしかない配列を渡すと要素が1つしかない配列が返ること")
	@Test
	void testStraightExchangeOneElement() {
		int[] array = { 5 };
		int[] expected = { 5 };

		int[] actual = MergeSort.mergeSortWrapper(array);
		assertThat(actual, is(expected));
	}

	@DisplayName("空の配列を渡すと空の配列が返ること")
	@Test
	void testStraightExchangeEmpty() {
		int[] array = {};
		int[] expected = {};

		int[] actual = MergeSort.mergeSortWrapper(array);
		assertThat(actual, is(expected));
	}

	@DisplayName("すでに昇順でソートされた配列を渡すとソートされた配列が返ること")
	@Test
	void testStraightExchangeAlreadySorted() {
		int[] array = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14 };
		int[] expected = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14 };

		int[] actual = MergeSort.mergeSortWrapper(array);
		assertThat(actual, is(expected));
	}

	@DisplayName("要素が重複した配列を渡すとソートされた配列が返ること")
	@Test
	void testStraightExchangeDuplicateElement() {
		int[] array = { 5, 3, 5, 2, 1, 5, 3, 2, 5, 3, 5 };
		int[] expected = { 1, 2, 2, 3, 3, 3, 5, 5, 5, 5, 5 };

		int[] actual = MergeSort.mergeSortWrapper(array);
		assertThat(actual, is(expected));
	}
}
```

# マージソートアルゴリズム

```java:MergeSort.java
public class MergeSort {

	private static int[] tempArray;

	/**
	 * マージソートのラッパーメソッド
	 * @param array
	 * @return sortedArray
	 */
	public static int[] mergeSortWrapper(int[] array) {
		int[] sortedArray = array.clone();
		tempArray = new int[sortedArray.length];
		sortedArray = mergeSort(sortedArray, 0, sortedArray.length - 1);
		tempArray = null;
		return sortedArray;
	}

	/**
	 * マージソート：再帰処理を使った分割統治でソートする
	 * @param array
	 * @param left
	 * @param right
	 * @return ソート済みの array
	 */
	private static int[] mergeSort(int[] array, int left, int right) {
		if (array.length <= 1 || left >= right) {
			return array;
		}

		int middle = (left + right) / 2;
		mergeSort(array, left, middle); // 左側を再帰的にソートしきる
		mergeSort(array, middle + 1, right); // 右側を再帰的にソートしきる
        // 最初に呼ばれたとき上記２つのmergeSort()が終わった時点でソート済みの2つの配列が存在している

		// 左半分をtempArrayにコピー
		for (int i = left; i <= middle; i++) {
			tempArray[i - left] = array[i];
		}

		int leftIndex = 0; // 左サブ配列のインデックス
		int rightIndex = middle + 1; // 右サブ配列のインデックス
		int sortedIndex = left; // マージされた配列のインデックス

		// 左と右のサブ配列をマージ
		while (leftIndex < (middle - left + 1) && rightIndex <= right) {
			if (tempArray[leftIndex] <= array[rightIndex]) {
				array[sortedIndex++] = tempArray[leftIndex++];
			} else {
				array[sortedIndex++] = array[rightIndex++];
			}
		}

		// 左サブ配列が残っているならコピー
		while (leftIndex < (middle - left + 1)) {
			array[sortedIndex++] = tempArray[leftIndex++];
		}

		return array;
	}
}
```

# やってること

再帰処理は頭がおかしくなりそうですが、 やっているのは divide and conquerです！！！！

1. `[5, 12, 7, 0, 1, 14, 6, 9, 8, 3, 2, 11, 4, 13, 10]` が与えられる
1. `[5, 12, 7, 0, 1, 14, 6]` と `[9, 8, 3, 2, 11, 4, 13, 10]` に分割
1. 左側の配列をソートするために分割する
1. `[5, 12, 7]` と `[0, 1, 14, 6]` に分割
1. `[5, 12, 7]` を `[5, 12]` と `[7]` に分割
1. `[5]` と `[12]` に分割 
1. `[0, 1, 14, 6]` を `[0, 1]` と `[14, 6]` に分割
1.  `[0]` と `[1]` に分割
1.  `[14]` と `[6]` に分割
1. 分割した左側の配列を統合とソート
1. `[5, 12]` に統合
1. `[5, 7, 12]` に統合
1. `[0, 1]` に統合
1. `[6, 14]` に統合
1. `[0, 1, 6, 14]` に統合
1. `[0, 1, 5, 6, 7, 12, 14]` に統合
1. 次に右側の配列をソートするするために分割する
1. `[9, 8, 3, 2]` と `[11, 4, 13, 10]` に分割
1. （めんどくさいので省略）
1. 2つの配列が出来上がる
1. `[0, 1, 5, 6, 7, 12, 14]` と `[2, 3, 4, 8, 9, 10, 11, 13, 10]`
1. 2つのソート済み配列を完全に統合する
1. `[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14]`