다중 방향 병합 vs 2 방향 병합

Question

externally merge sort 큰 파일을 작은 파일로 분할하고 정렬 한 다음 큰 파일을 다시 병합합니다.

병합 할 때 많은 양방향 병합 통과 또는 하나의 다중 방식 병합을 수행 할 수 있습니다.

어떤 접근 방식이 더 좋은지 궁금합니다. 그리고 왜?

Answer 1

일반적으로 하나의 다중 방향 병합이 더 좋습니다. 고려 세 개의 작은 파일 :

a1 
a2 
a3 

및

b1 
b2 
b3 

마지막

c1 
c2 
c3 

당신이 a와 b와 병합을 할 경우, 우리는 (말)

남아있어

a1 
b1 
a2 
b2 
b3 
a3 

및

c1 
c2 
c3 

마지막 병합은 정렬 된 목록을 만들 수 있지만 마지막 병합에 우리가 다시 a 및 b 항목을 방문해야하는 방법을 알 것입니다. 계단식 양방향 병합에서 낭비되는 것은 이러한 재 통합입니다.

대신 할 수있는 것은 단일 다중 방향 병합입니다. 그러나, 어떻게하는지 조심하십시오. 특히 각 커서를 스캔하여 최소값을 갖는 순진한 이중 루프를 피하십시오. 대신에 min-heap을 사용하십시오. 그러면 복잡성이 다시 O(n log n)이됩니다.