병합정렬(Merge Sort)

병합정렬(Merge Sort)

병합정렬은 전체 리스트를 두 개의 균등한 크기로 분할하면서 하나의 원소로 분할될때까지 계속해서 반복합니다. 분할을 끝내면 합병하는 과정을 거치면서 리스트를 정렬해나갑니다.

분할

정렬되지 않은 리스트를 하나의 단위로 각각 분할합니다.

병합

하나의 단위로 분할된 원소들을 비교해나가면서 병합을 진행합니다.

2개의 리스트를 병합할때 매번 sort를 진행하는데 2개의 리스트의 첫번째 자리부터 비교해나가면서 sort를 진행하면 됩니다.

python 코드

# 1. 분할
def merge_sort(arr):  # arr : 정렬이 안된 리스트
    if len(arr) <= 1:
        return arr
    mid = len(arr) // 2
    left = merge_sort(arr[:mid])
    right = merge_sort(arr[mid:])
    return merge(left, right)

# 2. 합병
def merge(left, right):
    l = r = 0
    sorted_list = []
    # 두 배열을 비교하면서 sort를 진행
    while l < len(left) and r < len(right):
        if left[l] < right[r]:
            sorted_list.append(left[l])
            l += 1
        else:
            sorted_list.append(right[r])
            r += 1
    # 남은 값들을 넣어줌
    sorted_list += left[l:]
    sorted_list += right[r:]
    return sorted_list

병합정렬(merge sort)의 특징

장점

• 안정적인 정렬방법
• 데이터의 분포에 영향을 덜받는다. 즉 입력데이터와 상관없이 정렬되는 시간은 동일하다(nlog n)

단점

• 임시 배열이 필요하다(sorted_list)
• 크기가 큰 리스트인경우 이동 횟수가 많아 시간적비용이 크다