|
|
|
|
머지 정렬 알고리즘
|
|
■ 머지 방법
- 두 정렬된 부분배열의 원소를 비교, 결합하여 하나의
정렬된 배열을 만든다.
- 두 부분 배열은 서로 인접하여 있으며 머지된 결과는
제자리에 남는다.
- 두 부분배열은 서로 인접하여 있기 때문에 이들의
위치를 표현하는데는 그들이 속해있는 배열명과 첫째
부분배열의 시작점과 끝점 그리고 두 번째 부분배열의
끝점을 나타내는 배열 첨자만 필요 (예)
A[1:3]과 A[4:6]을 머지하려면 배열의 이름인 A와 첨자인
1,3,6만을 함수 Merge에 전달하면 됨
- 두 개의 부분배열을 머지하는 데는 그 두 부분배열을
합한 것만큼의 여분의 메모리 공간이 필요
- 배열
B가 그 여분 공간으로 사용됨
|
|
|
