병합 정렬(Merge Sort)

전개

1. 리스트의 길이가 1 이하이면 이미 정렬된 것으로 본다. 그렇지 않은 경우에는
2. 분할(divide) : 정렬되지 않은 배열을 절반으로 잘라 비슷한 크기의 두 부분 배열로 나눈다.
3. 정복(conquer) : 각 부분 배열을 재귀적으로 병합 정렬을 이용해 정렬한다.
4. 결합(combine) : 두 부분 배열을 다시 하나의 정렬된 배열로 합병한다.

• 병합 정렬 알고리즘은 분할 정복(divide and conquer) 방식을 사용한다.

  분할 정복(divide and conquer): 큰 문제를 작은 문제로 나누어(분할하여) 푸는(정복하는) 방법

시간 복잡도

• O(${NlogN}$)

구현 코드

def merge_sort(numbers):
    """ 오름차순 병합 정렬을 실행합니다. """
    n = len(numbers)

    if n <= 1:
        return

    mid = n // 2
    left_group = numbers[:mid]
    right_group = numbers[mid:]

    merge_sort(left_group)
    merge_sort(right_group)

    left = 0
    right = 0
    now = 0

    while left < len(left_group) and right < len(right_group):
        if left_group[left] < right_group[right]:
            numbers[now] = left_group[left]
            left += 1
            now += 1
        else:
            numbers[now] = right_group[right]
            right += 1
            now += 1

    while left < len(left_group):
        numbers[now] = left_group[left]
        left += 1
        now += 1

    while right < len(right_group):
        numbers[now] = right_group[right]
        right += 1
        now += 1


if __name__ == '__main__':
    numbers = [6, 5, 6, 4, 3, 2, 1]

    merge_sort(numbers)

    print(numbers)

'''
출력 결과

[1, 2, 3, 4, 5, 6, 6]
'''

Ref

• 모두의 알고리즘 with 파이썬
• 합병 정렬