정렬 알고리즘 병합 정렬 (Mergesort) 해석

no_mkd

일.병합 정렬의 장단점 (pros and cons)

노력을 들여 이해하는 데는 이유가 있어야겠죠:

• 병합 정렬의 효율은 정점에 달했습니다: 시간 복잡도는 O(nlogn) 으로, 이는 비교 기반 정렬 알고리즘이 달성할 수 있는 최고 경지입니다
• 병합 정렬은 안정적인 알고리즘입니다 (즉, 정렬 과정에서 크기가 같은 요소는 정렬 전의 순서를 유지할 수 있습니다. 3212 를 오름차순 정렬한 결과는 1223 이며, 정렬 전후 두 개의 2 의 순서는 변하지 않습니다). 이 점은 어떤 시나리오에서 매우 중요합니다
• 병합 정렬은 가장 일반적인 외부 정렬 방법입니다 (정렬 대상 레코드가 외부 저장 장치에 있고 메모리에 모든 데이터를 담을 수 없을 때도 병합 정렬은 계속 적용 가능합니다. 물론 병합 정렬은 내부 정렬에도 마찬가지로 적용 가능합니다...)

단점:

• 병합 정렬은 O(n) 의 보조 공간이 필요하며, 이와 효율이 같은 퀵 정렬과 힙 정렬은 각각 O(logn) 과 O(1) 의 보조 공간이 필요합니다. 동종 알고리즘 중에서 병합 정렬의 공간 복잡도가 다소 높습니다

P.S.본 글에서는 가장 원시적인 "이로 병합"만 논의하며, 다로의 것은 이와 유사합니다

이.내부 원리

먼저 병합 정렬의 사상은: 분할 정복법이며, 퀵 정렬의 사상과 같습니다

알고리즘 사상: 무질서 -> 부분적으로有序 -> 전체적으로有序

병합 정렬에서 "분할"과 "병합"의 과정은 함께 결합되어 있습니다. 즉, 각 라운드에서 "분할"과 "병합"의 작업을 하고 있으며, 먼저 "분할"을 끝낸 다음 "병합"하는 것이 아닙니다 ("분할"은 매우 간단합니다. 그냥 이분 이분 더 이상 분할할 수 없을 때까지라고 생각하면, 그것은 잘못입니다. 분할하면 병합할 수 없게 됩니다. "분할"과 "병합"은 함께 결합되어 있음을 명심하세요)

병합 정렬의 과정을 한 폭의 그림으로 설명하는 것으로 충분합니다:

설명:P1 과 P2 를 비교하여 큰 (작은) 쪽을 P 에装入한 후 P1 또는 P2 를 오른쪽으로 이동하고 (누구를装入했는지 이동), 마지막으로 P 를 오른쪽으로 이동합니다

예를 들어 배열 a[n] 을 오름차순 정렬한다면 구체적인 과정은 다음과 같습니다:

1. 길이가 모두 n/2 인 2 개의 보조 공간을 신청하여 a 배열을装入합니다. 전반은 L 에, 후반은 R 에装入합니다
2. 설명 중의 방식으로 1 라운드의 비교를 수행합니다 (P 가 A 에서 C 로 이동하여 1 라운드 종료)

이제 1 라운드의 정렬을 마치고 무엇을 얻었는지 생각해봅시다:

1. 부분적으로有序를 달성했습니다 (전반 < 후반, 맞죠?)
2. 그 외에도, 매우 자연스럽게 정렬 대상 시퀀스를 이등분하여 재귀를 위한 준비를 했습니다

아직 명확하지 않나요? 그렇다면 몇 마디 더 있습니다:

1. 도시된 과정은 왜 길이 n 의 보조 공간이 필요한지를 설명합니다
2. L 과 R 이 각각 내부적으로有序하면 (같은 오름차순 또는 같은 내림차순), 그 후 1 라운드의 병합만 거치면 정렬이 완료됩니다 (잘 생각해보세요, 맞죠?)
3. 정렬 부분이 병합 부분입니다 (위에서 언급한 그 말을 기억하나요? "분할"과 "병합"의 과정은 함께 결합되어 있으며, 결코 분리해서 생각하면 안 됩니다. 그렇지 않으면 병합할 수 없게 된다는 것을 발견할 것입니다...)

삼.구현 세부사항

위의 설명이 아직 명확하지 않다면 예시를 들어 한 걸음씩 분석해봅시다:

정렬 대상 시퀀스가 a[] = {3, 2, 1, 4} 라고 가정하면 구체적인 과정은 다음과 같습니다:

P.S.정렬 대상 시퀀스가 홀수 개라면 어떻게 할까? 이것은 문제입니까? 단순히 분할된 전반이 후반보다 하나 적을 뿐이며, 단일 라운드 루프 제어는 P 포인터에 의해 수행되므로, 어떤 P1 에 대응하는 P2 가 비교할 수 없는 문제는 존재하지 않습니다

사.정리

병합 정렬은 외부 정렬이 필요한 시나리오에서 많이 사용되며, 그 외에도 내부 정렬에서 안정성을 보장해야 할 때도 병합 정렬을 채택합니다 (안정성을 요구하지 않는 내부 정렬은 일반적으로퀵 정렬또는 힙 정렬을 사용합니다. 전자는 정렬 대상 시퀀스가 기본적으로有序할 때 효율이 낮고, 후자는 힙의 유지보수가 문제입니다)