병합 정렬 알고리즘(Merge Sort)

병합 정렬

앞에서 살펴본 퀵 정렬과 같이 분할 정복 개념을 사용한 정렬이다. 둘의 차이점은 데이터를 분할 할때 병합정렬에서는 반드시 반으로 나눈다는 것이다. 따라서 N * log N의 성능을 보장하는 것이 병합 정렬 알고리즘이다. 그렇지만 평균적으로는 퀵정렬이 더 빠르다.

 

병합 정렬의 개념은 '일단 데이터를 모두 각각 반으로 쪼개고 본다!' 이다. 즉 데이터를 계속 쪼개서 각각의 데이터가 하나가 되었을 때부터 시작한다. 그림으로 한번 표현해보았다.

 

---

 

이제 모두 쪼개진 데이터로부터 시작해서 각각의 데이터를 병합(Merge) 해나갈 텐데, 두 집합의 데이터를 비교해서 정렬하여 병합한다.

따라서 병합의 단계가 진행될 때마다, 그 집합은 정렬이 되어있음이 보장된다. 이게 무슨 말이냐 하면,

 

 

 

데이터가 위와 같다고 생각하고 보면 길이가 1인 데이터 우선 7과 5를 비교한다. 그러면 5가 더 작기 때문에 5, 7 순서로 정렬된다. 2, 3을

비교하면 그대로 2, 3으로 된다. 그럼 이제 길이가 2인 것을 정렬할 때는 

 

 

 

5, 7 과 2, 3 배열의 데이터는 각각 집합안에서 정렬이 되어있다. 따라서 두 집합의 첫번째 원소중에 작은 것을 가져와서 아래 길이 4인 배열에다가 넣으면 된다. 다시말해서 각 집합안에서 정렬이 되었기 때문에 순서가 보장 되고, 각각의 집합에서 최솟값을 가져와서 배열을 만들기 때문에 새로 만드는 배열도 데이터의 정렬이 보장된다.

 

이렇게 분할된 집합을 정렬하는 데에는 리소스가 적게 들게된다.

위와 같은 작업을 수행하려면 각 집합과 새로운 배열을 가리킬 인덱스가 3개 필요하다.

 

 

처음에 j 인덱스에서 2를 가져와서 k인덱스에 넣는다. 다음에도 j에서 3을 가져와서 k에 넣고 i에서 차례대로 5, 7을 가져와서 k에 넣는다.

 

 

보다시피 데이터가 각 집합 안에서 정렬 된다.

나머지 과정도 그림으로 보도록하자.

 

 

이제 나머지 반도 정리가 완료 되었다. 길이 4인 배열이 두 개 생기게 되었는데 2 3 5 7 / 0 1 4 6 은 위에서 말한 것과 같이

각 집합안에서 정렬이 완료되어있다. 이제 두 집합을 최종적으로 병합하게 되면, 

 

 

깔끔하게 정렬이 되었다. 

시간복잡도를 시각적으로 살펴보자

 

 

아까 말했듯이 병합정렬은 각 분할 단계에서 데이터를 반으로 나누는 것이 보장되어 있기 때문에 재귀적으로 깊이 logN 만큼 연산을 수행한다. 그리고 분할된 데이터를 병합할 때 선형적으로 이미 정렬이 보장된 각각의 집합 중에 작은 데이터를 가져오기 때문에 N 만큼의 연산을 수행한다. 결국 N * logN 만큼의 연산을 수행하고 그만큼의 시간 복잡도를 갖게된다. 다만 각 집합을 병합할때 정렬하여 넣을 새로운 배열이 필요하기 때문에 퀵정렬에 비해 공간을 추가적으로 더 사용하게 된다. 

 

병합 정렬을 코드로 구현 해보자

 

 

merge 함수

 

 

 

mergeSort

 

코드에서도 볼 수 있듯이 데이터를 먼저 재귀적으로 반씩 나눈 후에 각 단계의 두 부분을 병합해준다. 

 

 

이 글은 아래 글과 이어집니다

https://charlie-junbeom-94043.tistory.com/42

힙 정렬(Heap Sort)

 

참조

https://m.blog.naver.com/PostView.naver?isHttpsRedirect=true&blogId=ndb796&logNo=221227934987 

7. 병합 정렬(Merge Sort)

 

틀린 것이 있으면 지적 부탁드립니다.