합병 정렬(Merge Sort)

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()