병합 정렬(Merge Sort)

원소 개수가 1 또는 0이 될 때까지 두 부분으로 쪼개고 쪼개서 자른 순서의 역순으로 크기를 비교해 병합해 나가는 정렬 방식

• stable sorting이다.
• 배열을 원소의 갯수가 1 이하가 될 때까지 나누기 위해 $log \,n$ 의 높이가 필요하고, 각 단계에서 정렬에 필요한 반복 횟수는 $n$이다. 따라서 시간복잡도는 $O(n\;log\,n)$이다.
• 데이터 크기만한 메모리가 더 필요하다. 따라서 공간 복잡도는 $O(n)$이다.

흔히 쓰이는 하향식 2-way 합병 정렬은 다음과 같이 작동한다.

1. 리스트의 길이가 1 이하이면 이미 정렬된 것으로 본다. 그렇지 않은 경우에는
2. 분할(divide): 정렬되지 않은 리스트를 절반으로 잘라 비슷한 크기의 두 부분 리스트로 나눈다.
3. 정복(conquer): 각 부분 리스트를 재귀적으로 합병 정렬을 이용해 정렬한다.
4. 결합(combine): 두 부분 리스트를 다시 하나의 정렬된 리스트로 합병한다. 이때 정렬 결과가 임시배열에 저장된다.
5. 복사(copy): 임시 배열에 저장된 결과를 원래 배열에 복사한다.

코드 구현

import java.util.Arrays;

public class MergeSort {

	static int[] sortedArr;

	public static void main(String[] args) {
		int[] arr = { 77, 32, 37, 17, 22, 8, 13, 42, 26 };
		sortedArr = new int[arr.length];

		System.out.println("정렬전: " + Arrays.toString(arr));
		mergeSort(arr, 0, arr.length-1);
		System.out.println("정렬후: " + Arrays.toString(arr));
	}

	// arr : 내가 정렬하고자 하는 배열 / left ,right 경계,위치
	public static void mergeSort(int[] arr, int left, int right) {
		if (left < right) {
			int mid = (left + right) / 2;
			mergeSort(arr, left, mid); // (1) 왼쪽 절반 분할
			mergeSort(arr, mid + 1, right); // (1) 오른쪽 절반 분할
			merge(arr, left, mid, right); // (2) 분할된 집합 병합
		}
	}

	public static void merge(int[] arr, int left, int mid, int right) {
		int L = left; // 왼쪽 구간 시작 인덱스
		int R = mid + 1; // 오른쪽 구간 시작 인덱스
		int idx = left; // 정렬된 원소 저장할 위치

		while (L <= mid && R <= right) {  // 어느 한 쪽이 끝까지 도달하지 않았을 때
        	// 분할된 부분들 중 더 작은 부분을 삽입
			if (arr[L] <= arr[R])
				sortedArr[idx++] = arr[L++]; // 값들을 넣고 증가시킨다.
			else
				sortedArr[idx++] = arr[R++];
		}

		// 왼쪽구간이 남았다면
		if (L <= mid) {    // (3)
			for (int i = L; i <= mid; i++)
				sortedArr[idx++] = arr[i];
		}
		// 오른쪽구간이 남았다면
		else {    // (3)
			for (int i = R; i <= right; i++)
				sortedArr[idx++] = arr[i];
		}

		// 정렬한 임시배열을 원 배열에 저장한다.
		for (int i = left; i <= right; i++)
			arr[i] = sortedArr[i];

		System.out.println(Arrays.toString(arr));

	}
}

정렬전: [77, 32, 37, 17, 22, 8, 13, 42, 26]
[32, 77, 37, 17, 22, 8, 13, 42, 26]
[32, 37, 77, 17, 22, 8, 13, 42, 26]
[32, 37, 77, 17, 22, 8, 13, 42, 26]
[17, 22, 32, 37, 77, 8, 13, 42, 26]
[17, 22, 32, 37, 77, 8, 13, 42, 26]
[17, 22, 32, 37, 77, 8, 13, 26, 42]
[17, 22, 32, 37, 77, 8, 13, 26, 42]
[8, 13, 17, 22, 26, 32, 37, 42, 77]
정렬후: [8, 13, 17, 22, 26, 32, 37, 42, 77]

(1)에서 mergeSort 메소드는 재귀를 이용해 right<=left가 될 때 까지(분할된 크기가 1 이하가 될 때까지) 분할을 진행한다. 분할이 모두 이루어졌으면 (1)의 메소드들은 실행할 내용이 없고, (2)의 merge 메소드를 실행하여 병합을 진행한다. sortedArr의 idx를 증가시켜가며, 오름차순의 경우 arr[L]과 arr[R]중 더 작은 것을 집어넣고 L 혹은 R을 증가시킨다.
(3)에서는 배열의 왼쪽과 오른쪽에 남은 것들을 마지막 순서에 집어넣는다.

과정

아래에서는 편의를 위해 원소를 인덱스로 설명하자면,

0. functioncall : mergeSort(0,8)
1. 0~8을 0~4, 5~8로 나눈다.
   • mergeSort(0,8) mergeSort(0,4)
2. 0~4를 0~2, 3~4로 나눈다.
   • mergeSort(0,8) mergeSort(0,4) mergeSort(0,2)
3. 0~2를 0~1, 2로 나눈다.
   • mergeSort(0,8) mergeSort(0,4) mergeSort(0,2) mergeSort(0,1)
4. mergeSort(0,1)에서 호출한 mergeSort(0,0)은 실행하지 않고 mergeSort(1,1)도 실행하지 않는다. merge(0,0,1)을 호출하여 arr의 0부터 1까지를 정렬한다.
   • mergeSort(0,8) mergeSort(0,4) mergeSort(0,2)
5. mergeSort(0,2)에서 mergeSort(0,1)을 끝냈으니 다음 줄에서 mergeSort(2,2)를 호출하지만, left==right이므로 실행하지 않는다. 다음 줄에서 merge(0,1,2)를 실행하여 0부터 2까지 정렬한다.
   • mergeSort(0,8) mergeSort(0,4)
6. mergeSort(0,4) 에서 실행한 mergeSort(0,2)가 완료되었으니 mergeSort(3,4)를 호출한다.
   • mergeSort(0,8) mergeSort(0,4) mergeSort(3,4)
7. mergeSort(3,4)에서 mergeSort(3,3)는 left==right이므로 실행하지 않고, mergeSort(4,4) 또한 실행하지 않는다. 다음 줄에서 바로 merge(3,3,4)를 실행한다.

........

정렬전: [77, 32, 37, 17, 22, 8, 13, 42, 26]
mergeSort([77, 32, 37, 17, 22, 8, 13, 42, 26], 0, 8)
mergeSort([77, 32, 37, 17, 22, 8, 13, 42, 26], 0, 4)
mergeSort([77, 32, 37, 17, 22, 8, 13, 42, 26], 0, 2)
mergeSort([77, 32, 37, 17, 22, 8, 13, 42, 26], 0, 1)
mergeSort([77, 32, 37, 17, 22, 8, 13, 42, 26], 0, 0)
mergeSort([77, 32, 37, 17, 22, 8, 13, 42, 26], 1, 1)
merge([77, 32, 37, 17, 22, 8, 13, 42, 26], 0, 0, 1)
[32, 77, 37, 17, 22, 8, 13, 42, 26]
mergeSort([32, 77, 37, 17, 22, 8, 13, 42, 26], 2, 2)
merge([32, 77, 37, 17, 22, 8, 13, 42, 26], 0, 1, 2)
[32, 37, 77, 17, 22, 8, 13, 42, 26]
mergeSort([32, 37, 77, 17, 22, 8, 13, 42, 26], 3, 4)
mergeSort([32, 37, 77, 17, 22, 8, 13, 42, 26], 3, 3)
mergeSort([32, 37, 77, 17, 22, 8, 13, 42, 26], 4, 4)
merge([32, 37, 77, 17, 22, 8, 13, 42, 26], 3, 3, 4)
[32, 37, 77, 17, 22, 8, 13, 42, 26]
merge([32, 37, 77, 17, 22, 8, 13, 42, 26], 0, 2, 4)
[17, 22, 32, 37, 77, 8, 13, 42, 26]
mergeSort([17, 22, 32, 37, 77, 8, 13, 42, 26], 5, 8)
mergeSort([17, 22, 32, 37, 77, 8, 13, 42, 26], 5, 6)
mergeSort([17, 22, 32, 37, 77, 8, 13, 42, 26], 5, 5)
mergeSort([17, 22, 32, 37, 77, 8, 13, 42, 26], 6, 6)
merge([17, 22, 32, 37, 77, 8, 13, 42, 26], 5, 5, 6)
[17, 22, 32, 37, 77, 8, 13, 42, 26]
mergeSort([17, 22, 32, 37, 77, 8, 13, 42, 26], 7, 8)
mergeSort([17, 22, 32, 37, 77, 8, 13, 42, 26], 7, 7)
mergeSort([17, 22, 32, 37, 77, 8, 13, 42, 26], 8, 8)
merge([17, 22, 32, 37, 77, 8, 13, 42, 26], 7, 7, 8)
[17, 22, 32, 37, 77, 8, 13, 26, 42]
merge([17, 22, 32, 37, 77, 8, 13, 26, 42], 5, 6, 8)
[17, 22, 32, 37, 77, 8, 13, 26, 42]
merge([17, 22, 32, 37, 77, 8, 13, 26, 42], 0, 4, 8)
[8, 13, 17, 22, 26, 32, 37, 42, 77]
정렬후: [8, 13, 17, 22, 26, 32, 37, 42, 77]

출처

---

https://namu.wiki/w/%EC%A0%95%EB%A0%AC%20%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98#s-2.2.1
https://ko.wikipedia.org/wiki/%ED%95%A9%EB%B3%91_%EC%A0%95%EB%A0%AC
https://kangworld.tistory.com/74 (시간복잡도)