병합 정렬(Merge Sort)

정렬하고자 하는 데이터의 모임을 비슷한 크기의 두 부분으로 반복하여 나눈 뒤, 나누어진 부분 데이터들을 정렬한 다음에 다시 병합하면서 하나의 정렬된 데이터 모임으로 만드는 방법.

 

1940년에 존 폰 노이만(John von Neumann)이 개발한 병합 정렬(Merge Sort)의 특징은 입력 데이터의 정렬 여부와는 관계가 없이 맵리듀스와 같은 빅데이터 알고리즘 처럼 분할 및 정복 전략을 사용합니다.

 

병렬 정렬 순서]

1. 입력된 리스트를 크기가 같은 두 부분으로 나눈다.

2. 나뉜 부분의 크기가 1이 될 때까지 반복해서 나눈다.

3. 각 부분을 정렬한 뒤 병합하여 최종적으로 정렬된 리스트를 반환한다.

 

Python]

def MergeSort(list):
    if len(list)>1:
        mid = len(list)//2 #리스트르 반으로 나눈다.
        left = list[:mid]
        right = list[mid:]

        #나뉜 부분의 크기가 1일 될 때까지 반복한다.
        MergeSort(left)
        MergeSort(right)

        a = b = c = 0
        while a<len(left) and b<len(right):
            if left[a] < right[b]:
                list[c] = left[a]
                a += 1
            else:
                list[c] = right[b]
                b += 1
            c += 1

        while a<len(left):
            list[c] = left[a]
            a += 1
            c += 1

        while b<len(right):
            list[c] = right[b]
            b += 1
            c += 1

        return list

 

 

 

출처]

국립국어원 : 병합 정렬

프로그래머가 알아야 할 알고리즘 40(길벗) : 병합 정렬(p 083)

 

 

참고문제]

Python 329제] 병합 정렬

 

 

 

※ 10월 25일은 독도의 날입니다.

 

대한민국의 아름다운 영토, 독도