Computer ScienceAlgorithmTheory

10. Merge 정렬 알고리즘

Merge 정렬 알고리즘

퀵 소트가 피벗을 어떻게 선택하냐에 따라 속도가 달라지는 단점을 상쇄하는 알고리즘

배열은 반으로 나눠 재귀적으로 정렬하고 정렬된 두 배열을 원소 하나씩 비교해서 병합하는 방식.
주어진 배열만큼 새로운 배열을 사용해야 하기 때문에 not in-place 알고리즘이다.

  1. 먼저 중간 인덱스를 찾는다.

  2. 중간 인덱스를 기준으로 나눠서 두 배열을 재귀적으로 정렬한다.

  3. 정렬된 두 배열의 첫 요소부터 하나씩 서로 비교해서 더 작은 값은 새로 만든 배열에 추가한다.

  4. 추가된 요소의 배열은 다음 인덱스로 넘어가고, 다시 각 배열의 원소 하나와 비교한다.

  5. 어느 한쪽의 배열이 모두 비교될 때까지 반복한다.

  6. 어느 한쪽 배열이 모두 새 배열에 추가되고 나면, 다른 쪽의 배열을 다 새 배열에 추가한다.

  7. 원래 배열의 내용을 새 배열의 내용으로 덮어쓴다.

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    def merge_sort(A, first, last):
        #1.~2.
        if first >= last : return
        middle = (first+last)//2
        merge_sort(A,first, middle)
        merge_sort(A, middle+1, last)
        
        #3.~5.
        B = []
        i = first
        j = middle+1
        while i <= middle and j <= last:
            if A[i] <= A[j]:
                B.append(A[i])
                i+=1
            else:
                B.append(A[j])
                j+=1
        
        #6.~7.
        for i in range(i, middle+1): B.append(A[i])
        for j in range(j, last+1): B.append(A[j])
        for k in range(first, last+1): A[k] = B[k-first]

수행시간
T(n) = 2*T(n/2) + cn = O(n log n) 상황에 관계 없이 성립하므로, 퀵 소트보다 좋다.

Share