Sorting - Merge Sort / Heap Sort

1. Merge Sort

• 1) Merge
  • 정렬되지 않은 A, B 두 배열이 주어졌을 때 하나의 정렬된 배열 C를 만든다.
  • A, B 각각의 맨 앞 원소를 비교해 더 작은 값을 C로 옮기는 과정을 반복한다.
  • W(n) = n-1  (맨 마지막 원소는 비교 없이 옮기기 때문)
• 2) Merge Sort
  • 의사코드
    void mergeSort(배열 E, int first, int last)
        if(first<last)
            int mid=(first+last)/2
            mergeSort(E, first, mid)   //재귀
            mergeSort(E, mid+1, last)    //재귀
            merge(E, first, last)
  • W(n) = W(n/2)+W(n/2)+W_merge(n) ∈ θ(nlogn)

2. Heap Sort

(이어서)