u 두 개의 정렬된 화일을 하나의 큰 정렬된 화일로 합병함
u 합병 정렬은 퀵 정렬과 마찬가지로 분할 정복 방식의 알고리즘임
u 두 부분배열의 크기가 동일하도록 분할함
u 최악의 경우에도 N 개의 원소를 가진 화일을 정렬하는 N logN 에 비례하는 시간이 소요됨
u 순차적 방식에 의해 데이터를 접근함
u 연결 리스트와 같이 순차 접근이 유일한 접근 방법일 경우 사용 가능
u N 에 비례하는 추가 기억장소가 필요함
u 안정적이지만 제자리 정렬은 아님
MergeSort(a[], l, r)
if (r > l) then {
m ← (r+l)/2;
MergeSort(a[], l, m);
MergeSort(a[], m+1, r);
Merge(a[], l, m, r);
}
end MergeSort()
Merge(a[], l, m, r])
i ← l; j ← m+1; k ← l;
while (i ≤ m and j ≤ r) do {
if (a[i] < a[j]) then {
b[k] ← a[i];
k ← k+1; i ← i+1;
}
else {
b[k] ← a[j];
k ← k+1; j ← j+1;
}
}
if (i > m) then
for (p ← j; p ≤ r; p ← p+1) do {
b[k] ← a[p];
k ← k+1;
}
else
for (p ← i; p ≤ m; p ← p+1) do {
b[k] ← a[p];
k ← k+1;
}
for (p ← l; p ≤ r; p ← p+1) do
a[p] ← b[p];
end Merge()