[알고리즘]MergeSort(병합정렬)

Merge Sort는 수열을 하나의 수가 될 때까지 분할을 한 후 다시 병합하는 정렬 방식이다.

Merge Sort는 크게 2가지의 과정을 거친다.

첫 번째 과정인 분할 과정에서는 수열을 분할(divide)하는 과정이다. Merge Sort에서는 size가 n인 배열이 있으면, [1 ~ n/2]의 배열과, [n/2 +1 ~ n] 으로 나누는 과정을 재귀를 통해 size가 1이 될 때까지 반복을 한다.

- Merge Sort의 원리

추가하여 설명을 하면, 처음 size가 7인 배열을 정렬을 할 경우, 1~4, 5~7의 원소를 갖는 배열로 나눈다. 나눌 때 배열이 홀수 이므로, 앞의 배열은 4개, 뒤의 배열은 3개로 나누게 된다. 분열을 한 후 재귀 함수를 통해 각각의 배열을 다시 1~2, 3~4, 5~6, 7의 원소를 갖는 배열로 나누고, 다시 한번 재귀함수를 통해 1, 2, 3, 4, 5, 6, 7, 8의 배열로 나눈다.

분할을 하여 모든 배열이 size가 1이 되면 두 번째 과정인 결합(combine)을 한다. 결합을 할 때는 두개의 배열의 처음 원소를 비교를 해서 작은 값을 새로운 배열에 넣는 과정을 반복하며 진행을 한다. 결합을 하는 과정은 아래와 같다. 

- Merge Sort의 동작 방식

각 단계에서 두개의 배열을 정렬을 하며 결합을 한다.

두 개의 배열을 결합할 때는 각각의 배열은 전 단계에서 이미 정렬이 된 상태이기 때문에 맨 앞의 원소들만 비교를 하여 병합을 한다. 각각의 배열을 결합을 하며 정렬을 하는 과정은 아래와 같다.

1.     A의 첫 번째 원소인 3과, B의 첫 번째 원소인 1을 비교한다. 1이 더 작기 때문에 C배열에 1을 넣는다.

2.     A의 첫 번째 원소인 3과, B의 두 번째 원소인 2을 비교한다. 2이 더 작기 때문에 C배열에 2을 넣는다.

3.   A의 첫 번째 원소인 3과, B의 세 번째 원소인 5을 비교한다. 3이 더 작기 때문에 C배열에 3을 넣는다.

4.     A의 두 번째 원소인 4과, B의 세 번째 원소인 5을 비교한다. 4이 더 작기 때문에 C배열에 4을 넣는다.

5. A의 세 번째 원소인 6과, B의 세 번째 원소인 5을 비교한다. 5이 더 작기 때문에 C배열에 5을 넣는다

6. 1.     A의 세 번째 원소인 6과, B의 네 번째 원소인 7을 비교한다. 6이 더 작기 때문에 C배열에 6을 넣는다.

7. 1.     A의 네 번째 원소인 8과, B의 네 번째 원소인 7을 비교한다. 7이 더 작기 때문에 C배열에 7을 넣는다.

8. 1.     A의 네 번째 원소인 8과, B의 다섯 번째 원소인 9을 비교한다. 8이 더 작기 때문에 C배열에 8을 넣는다.

9. 1.     A의 다섯 번째 원소인 10과, B의 다섯 번째 원소인 9을 비교한다. 9이 더 작기 때문에 C배열에 9을 넣는다.

10. 1.     B 배열의 더 이상 원소가 없기 때문에 A배열의 남은 원소를 C 배열에 넣는다.

- Merge Sort의 시간 복잡도

Merge sort의 time complexity를 계산하기 분석하기 위해 worst-case의 경우를 생각한다.

Size가 n인 배열을 merge sort를 통하여 정렬을 할 경우, 분할을 한 후, 결합을 하는 과정에서 총 의 결합 과정을 거친다. 또한 각각의 결합 과정은 최대 n번의 비교와 정렬 과정을 거친다. 그래서 merge sort의 time complexity는  θ ()이 된다. Merge sort의 경우는 insertion sort와 다르게 어떠한 경우에도 n 의 연산 횟수를 거치게 된다.

 Input이 증가할수록 시간이 오래 걸리지만,  의 time complexity 때문에 상대적으로 시간이 증가하는 폭이 적다. Merge sort의 경우 input의 정렬 정도가 running time에 크게 영향을 미치지 않는다. 그 이유는 정렬을 할 때 정렬의 정도가 높은 input이든, 정렬의 정도가 낮은 input이든 똑 같은 단계의 정렬방법과 똑 같은 연산 횟수를 하기 때문이다. 하지만 나뉘어진 두 개의 array에서 한 array의 정렬이 빨리 끝나는 input이 입력되면 더 이상 비교를 하지 않기 때문에 running time이 줄어들 수 있다. 하지만 이러한 차이는 input size가 커지면 무시할 수 있을 정도이다.

- Input Size에 따른 running time

Merge sort의 경우에는 input의 정렬 정도에 영향을 받지 않기 때문에 랜덤으로 값을 넣어주었다.

아래의 표는 input size를 바꿔가면서 running time을 측정한 결과 표이다.

Input size	Running time (milli seconds)
1	1
2,000,000	1,269
4,000,000	4,343
6,000,000	6,715
8,000,000	7,728
10,000,000	9,522

Input size를 2,000,000 부터 확인을 하였는데, 2,000,000 보다 낮은 값에서는 running time이 너무 낮게 나와 비교를 하기 힘들었기 때문이다.

Input size가 늘어날수록 running time이 비례해서 늘어나는 것을 확인 할 수 있다.

- 정렬 정도에 따른 running time

같은 환경에서 running time을 측정하기 위해, input size를 10,000,000개로 통일을 해주었다. 하지만 정렬 정도를 다르게 하기 위해 내림차순, 오름차순, 랜덤으로 input 을 넣어주었다.

 아래의 표는 정렬 정도에 따른 running time을 측정한 표이다.

정렬 단계	Input number	Running time (milli seconds)
내림차순	10,000,000 9,999,999 … 2 1	4717
Random	Random	8480
Random	Random	8419
Random	Random	8431
오름차순	1 2 … 9,999,999 10,000,000	4897

 내림차순, 오름차순으로 input값을 넣으면 하나의 array가 먼저 정렬이 되기 때문에 다른 array와 비교를 할 필요가 없어진다. 그러므로 random으로 input값을 넣었을 때보다 속도가 빠른 것을 확인할 수 있었다.

아래의 코드는 차이가 생기게 되는 코드이다. 내림차순과 오름차순의 경우에는 병합을 할 때 두 배열 중, 한 배열의 모든 원소는 다른 배열의 모든 원소보다 작게 되는 특징이 생긴다. 그러므로 내림차순과 오름차순의 경우에는 프로그램이 실행 될 때, 한 배열의 모든 원소가 새로운 배열에 입력된 후 비교를 할 필요가 없기 때문에 비교 횟수가 적게 된다. 그래서 내림차순과 오름차순의 경우 running time이 감소하는 결과가 나타났다.

if (i >= array1.size()) { // array1의 모든 원소가 정렬됬을 경우

             newArray.add(array2.get(j));      // newArray에 array2의 첫번째 넣는다.

             j++;

} else if (j >= array2.size()) { // array2의 모든 원소가 정렬됬을 경우

             newArray.add(array1.get(i));      // newArray에 array1의 첫번째 원소를 넣는다.

             i++;

} else {

             if (array1.get(i) > array2.get(j)) { // array1의 첫번째 원소가 array2의 첫번째 원소보다 클 경우

                           newArray.add(array2.get(j));      // newArray에 array2의 첫번째 넣는다.

                           j++;

             } else { // array1의 비교 원소가 array2의 비교 원소보다 작을 경우

                           newArray.add(array1.get(i));      // newArray에 array1의 첫번째 원소를 넣는다.

                           i++;

             }

}

내림차순, 오름차술의 경우 한 배열이 먼저 정렬이 된 후, 다른 배열이 정렬되므로 비교 횟수가 줄게 되어 running time이 줄게 된다. 하지만 이러한 차이는 상수에 따른 차이로 더 많은 input을 넣었을 경우는 무시를 할 수 있는 정도이다.

- Merge Sort와 Insertion Sort의 비교

시간 복잡도를 봤을 때, Merge Sort는 O(nlogn), Insertion Sort는 O(n^2)의 시간 복잡도를 갖는다. 보통 input이 30 이상일 때부터 Merge Sort가 빨라진다.

 하지만 Insertion Sort의 경우에는 input 값이 정렬되어 있을 수록 running time이 빨라진다.

 또한 Insertion Sort의 경우에는 추가적인 memory가 필요하지 않다. 하지만 Merge Sort의 경우에는 input size만큼의 추가적인 memory가 필요하다.

 Merge Sort의 경우에는 input의 정렬정도와 관련없이 어느정도의 성능을 보장해준다는 장점이 있다.

	장점	단점
Merge Sort	Insertion Sort에 비해 속도가 빠르다.(input size가 30 이상일 경우) input의 정렬 정도에 관련없이 어느 정도의 성능을 보장해준다.	작은 input size에 대해 Insertion Sort보다 속도가 느리다. 이미 정렬되어 있는 Input이라도 항상 같은 횟수의 연산을 한다. 추가적인 Memory가 필요하다.
Insertion Sort	작은 input size에 대해 Merge Sort보다 속도가 빠르다. 이미 정렬되어 있는 Input에 관해서 속도가 빠르다.  추가적인 Memory가 필요하지 않다.	Merge Sort에 비해 정렬 속도가 느리다 (input size가 30 이하일 경우)

- 소스코드

https://github.com/wkdgusdn3/MergeSort