|머지정렬 개념 | 머지정렬 알고리즘| 머지정렬 분석 |

■ 머지 정렬 개념

• 이미 순서적으로 배열된 두 개의 파일에서 레코드의 배열 순서에 따라 차례로 한 레코드씩 가져다 비교하여 작은 키 값을 가지는 레코드를 새로운 병합 파일에 출력하고, 작은 레코드를 가져온 파일에서 다음 순서의 레코드를 가져와 이전에 비교한 큰 키 값을 가진 레코드와 비교하는 과정을 반복 수행하므로 완전히 순서적으로 배열된 한 개의 파일을 만드는 것을 의미

• 머지 정렬(merge sort:합병 정렬)은 퀵 정렬과 마찬가지로 분할 정복 방식의 알고리즘

• 퀵 정렬에서는 분할되는 두 부분배열의 크기가 다를 수도 있고 이것 때문에 최악의 성능이 O(n2)으로 되었는데 머지 정렬에서는 두 부분배열의 크기가 항상 같게 분할 됨.

• 머지 정렬의 수행시간은 최악의 경우에도 O(NlogN)

• 머지 정렬은 별도의 임시 기억장소(배열)가 필요

• 실제로는 수행시간이 많이 걸리며, 외부정렬에 주로 활용