[알고리즘] 합병정렬 (Merge Sort) 개념 정리 및 코드 리뷰

감자 코딩에 감자 개발자입니다.  이번에 살펴본 내용은 알고리즘의 Sort중 하나인 합병정렬(Merge Sort)입니다.

1.합병 정렬(Merge Sort) 시간복잡도와 공간복잡도 

합병정렬 (InsertSort)의 시간복잡도는 밑이 2 인 O(nlogn)

왜 이렇게 시간복잡도가 나올까요?

바로 합병정렬의 가장큰 특징인 분할후 -> 합병이라는 것때문입니다.

N -> N/2 형식으로 나누게되므로 계속분할되면 nLogN만큼의 복잡도가 나오게됩니다.

2. 합병 정렬 원리

합병정렬이란? 전체 원소를 하나의 단위로 분할 한후 분할한 원소를 다시 합병하는 방식이다.

원리) 

1. 전체 원소를 1로 분할할때 까지 분할하여 계속해서 진행한다.

2. 다 나누어 졌으면, 그 원소들을 다시 비교하면서 Merge한다.

- 예시

40 10 60 20 80 30 70 50

과정 1 ) 분할

원소들을 1이 될때 까지 분할 합니다. " | " 분할 선

40 10 60 20 80 30 70 50

40 10 60 20 | 80 30 70 50

40 10 | 60 20 | 80 30 | 70 50

40 | 10 | 60 | 20 | 80 | 30 | 70 | 50

과정 2)  첫번째 병합 

최종적으로 원소들이 40 | 10 | 60 | 20 | 80 | 30 | 70 | 50 분할된것을 확인 할 수있습니다.

이제 역으로 분할한것들을 다시 병합하는 과정을 진행합니다.

* 40 | 10 을 비교합니다. -> (40 > 10 ) 10 40 

* 60 | 20 을 비교합니다.-> (60 > 20) 20 60

* 80 | 30 을 비교합니다.-> (80 > 30) 30 80

* 70 | 50 을 비교 합니다.-> (70 > 50) 50 70

첫번째 병합 : 10 40 | 20 60 | 30 80 | 50 70

과정 3) 두번째 병합

* 10 40 | 20 60 -> 10 과 20을 맨처음비교 해줍니다. (10 > 20)이므로 10 이 맨앞으로 나오게됩니다.

그리고, 현재 10 이 사라졌으니 40 과 20을 비교해줍니다. 여기서 주의할것은 바로 20이 나오지 않고 20과 40을 또 비교 해야한다는것입니다.

(40 > 20)이므로, 20 이 앞으로 나오게 됩니다. 

이제 40 과 60을 비교해줍니다. (40 > 60) 40이 앞으로 먼저 나오게 되고, 그 이후에 60이 나오게됩니다.

최종 정렬 : 10 20 40 60 | ? (아직 합병되지 않는 원소)

* 30 80 | 50 70 을 비교합니다. (30 > 50) 비교합니다. 30이 맨앞으로 나오게 됩니다.

그리고 80과 50을 비교합니다 (80 > 50) 50이 맨앞으로 나오게 됩니다.

이제 80과 70을 비교 하게 됩니다 ( 80 > 70) 70이 맨앞에 나오게 되고, 그이후에 80이 나오게 됩니다.

최종 정렬 : 10 20 40 60 | 30 50 70 80

과정 4) 세번째(마지막) 병합

이제 세번째 마지막 병합을 해보겠습니다.

최종 정렬 : 10 20 40 60 | 30 50 70 80

10 20 40 60 | 30 50 70 80

* 10 20 40 60 | 30 50 70 80

10과 30 을 비교 합니다. (10>30) 10이 맨앞으로 나오게 됩니다.

최종 정렬 : 10

20과 30 을 비교합니다. (20>30) 20이 맨앞으로 나오게 됩니다.

최종정렬 : 10 20 

40과 30을 비교합니다.. (40 > 30) 30이 맨앞으로 나오게 됩니다.

최종정렬 : 10 20 30

40과 50을 비교 합니다. (40 > 50) 40이 맨앞으로 나오게 됩니다.

최종정렬 : 10 20 30 40 

60과 50을 비교합니다. (60> 50) 50 이 맨앞으로 나오게 됩니다.

최종정렬 : 10 20 30 40 50

60과 70을 비교 합니다. (60> 70) 60이 맨앞으로 나오게 됩니다.

최종 정렬 : 10 20 30 40 50 60 

이제 나머지 70과 80을 비교하여 나오면 되는데, 이미 정렬되어있는상태이므로 확인하는 과정은 필요없습니다.

따라서, 순서대로 70과 80이 나오게 됩니다.

최종적으로, 최종정렬 : 10 20 30 40 50 60 70 80 순으로 정렬이 오름차순으로 잘 정렬된것을 확인 할 수 있습니다.

3. 합병 정렬의 코드