[정렬 알고리즘][파이썬] 병합 정렬

병합 정렬(merge sort)은 정렬하고 싶은 수열을 두 개의 수열(거의 같은 길이)로 분할해 갑니다. 더 이상 분할되지 않는 상태에 이르면(즉, 각 그룹이 한 개의 숫자가 된 경우) 그룹들을 병합(merge) 해 나갑니다. 병합할 때에는 정렬이 끝난 두 개의 수열을 병합해서 정렬이 끝난 하나의 수열로 만듭니다. 이것을 전체가 하나의 그룹이 될 때까지 반복합니다. - 책 알고리즘 도감

 

 

 

1. 수열을 반씩 분할해 나갑니다.

 

 

2. 병합하면서 정렬하는 작업을 반복합니다.

6과 4를 병합하면서 [4, 6]으로 정렬합니다. 그리고 3과 7을 병합하면서 [3, 7]으로 정렬합니다.

 

 

 

 

[4, 6]과 [3, 7]을 병합할 때처럼 2개 이상의 숫자를 포함하고 있는 그룹들을 서로 병합할 때는 선두의 숫자를 비교해서 작은 숫자를 이동시킵니다,

1. 4와 3을 비교하고 4 > 3 이므로 3을 이동시킵니다.

2. 그 다음 선두인 4과 7을 비교하고 4 < 7 이므로  4를 이동시킵니다.

3. 남은 6과 7을 비교하고 6 < 7 이므로 6을 이동킵니다.

4. 마지막으로 7을 이동시킵니다.

 

 

 

---

 

 

중간 단계를 생략했지만 위의 단계를 계속 반복해주면 위의 사진처럼 정렬이 될 것이라는 것을 직관적으로 알 수 있을 것입니다.

 

 

 

[병합정렬 코드] [파이썬]

merge_sort 함수

merge 함수

병합 정렬 코드는 두 함수(merge_sort, merge)로 구성되어있습니다.

merge_sort는 정렬되기 전의 리스트를 분할하고 merge함수를 사용하는 함수입니다.

merge함수는 매개 변수로 들어온 두 리스트를 병합과 정렬을 동시에 해주는 함수입니다.

---

<해설>

병합 정렬에서 숫자를 분할해 갈 때는 계산 시간이 걸리지 않습니다. (처음부터 분할된 상태라고 생각해도 좋습니다.) 두 개의 정렬이 끝난 수열을 병합하는 부분은, 선두의 수를 비교해서 작은 쪽을 위로 올리는 것을 반복하는 것이 전부이므로 두 수열의 길이에 따라 달라집니다. 따라서 하나의 층에서 병합 계산 시간은 그 층에 있는 숫자의 수가 됩니다.

그런데 그림을 보면 알겠지만, 어떤 층을 봐도 숫자는 n개이므로 각 층의 계산 시간은 O(n)이 됩니다. n개의 숫자를 하나가 될 때까지 반씩 분할했을 때의 층수는 log2n이 되므로 층수는 전부 log2n층이 됩니다. 즉, 전체 계산 시간은 O(n log n)이 됩니다. 이것은 앞 절에서 본 힙 정렬과 같은 시간입니다.

 

 

참고 - 책 알고리즘 도감