합병 정렬

합병 정렬은 분할 정복 알고리즘을 이용한 정렬 방법이다.

분할 정복은 큰 문제를 작은 문제로 쪼개어 작은 단위의 문제를 먼저 해결하면서 병합시켜 마지막으로 가장 큰 문제를 해결하는 문제 풀이 방법이다.

합병 정렬의 과정은 크게 배열을 분할하는 부분과 분할된 배열을 다시 합병하는 부분으로 나뉘어 진다.

분할에서는 배열을 두 개의 배열로 분할한다.
합병에서는 두 배열을 정렬을 하면서 합친다. 

	public class MergeSort {
	public int[] sort(int[] arr) {
	return divide(arr);
	}
	public int[] divide(int[] arr) {
	if ( arr.length == 1) {
	return arr;
	}
	int[] left = new int[(arr.length / 2)];
	int[] right = new int[arr.length - (arr.length / 2)];
	for (int i = 0; i < arr.length; i++) {
	if ( i < (arr.length / 2) ) {
	left[i] = arr[i];
	} else {
	right[i - (arr.length / 2)] = arr[i];
	}
	}
	left = divide(left);
	right = divide(right);
	return merge(left, right);
	}
	private int[] merge(int[] left, int[] right) {
	int leftIndex = 0;
	int rightIndex = 0;
	int[] merged = new int[left.length + right.length];
	for (int i = 0; i < merged.length; i++) {
	if ( left[leftIndex] <= right[rightIndex] ) {
	merged[i] = left[leftIndex];
	leftIndex++;
	if ( leftIndex == left.length ) {
	for (int j = i+1; j < merged.length; j++) {
	merged[j] = right[rightIndex];
	rightIndex++;
	}
	break;
	}
	} else {
	merged[i] = right[rightIndex];
	rightIndex++;
	if ( rightIndex == right.length ) {
	for (int j = i+1; j < merged.length; j++) {
	merged[j] = left[leftIndex];
	leftIndex++;
	}
	break;
	}
	}
	}
	return merged;
	}
	public static void main(String[] args) {
	MergeSort selectionSort = new MergeSort();
	System.out.println(Arrays.toString(selectionSort.sort(new int[]{7, 3, 8, 3, 6, 9, 4, 65, 89})));
	}
	}

view raw MergeSort.java hosted with ❤ by GitHub

시간복잡도는 분할에서 log2(N), 합병에서 N으로 분할이되는 만큼 다시 합병하기 때문에 둘을 곱하여 N*log2(N)이 된다.

성능이 선택, 버블, 삽입 정렬과 비교하여 효율적이고 안정적이기 때문에 자주 사용되는 정렬 방법 중 하나이다.
Java의 Arrays.sort() 및 Python sorted() 또한 합병 정렬과 삽입 정렬의 조합으로 작동한다.