[Python] 정렬 / 병합 정렬(Merge Sort)

병합 정렬

정렬 안되어 있는 리스트의 크기가 각각 1이 될때까지 리스트를 반으로 나눕니다. (분할)
나뉜 리스트를 다시 정렬하면서(정복) 결합하는 방식입니다.

병합 정렬 과정

• 복사를 위해 추가적인 리스트가 필요합니다.
• 리스트를 더이상 분해되지 않을 때까지, 재귀호출을 통해 분할합니다.
• 2개의 부분 리스트의 값들을 서로 비교하며 작은 값들을 먼저 새로운 리스트에 복사합니다.
• 각 단계를 마치게 되면, 값을 복사한 리스트를 원래의 리스트로 옮깁니다. 반복

2개의 부분리스트를 새로운 리스트에 정복, 결합하는 과정

병합 정렬

# 리스트 분할
def merge_sort(seq, left, right):
    # 더이상 쪼개지지 않을 경우
    if left >= right:
        return

    mid = (left + right) // 2
    merge_sort(seq, left, mid)
    merge_sort(seq, mid + 1, right)
    merge(seq, left, mid, right)          # 리스트 정복, 결합

# 리스트 정복, 결합
def merge(seq, left, mid, right):
    #print("left : {}\nright : {}".format(left, right))
    temp = [0] * len(seq)     # 정렬결과를 복제할 리스트
    i = left
    j = mid + 1
    k = left                  # temp리스트에서 가장 왼쪽부터 인덱스 이동

    # 작은 순서대로 temp 배열에 복사
    while i <= mid and j <= right:
        if seq[i] < seq[j]:
            temp[k] = seq[i]
            i += 1
        else:
            temp[k] = seq[j]
            j += 1
        k += 1

    # i가 아직 안끝났을 경우
    while i <= mid:
        temp[k] = seq[i]
        i += 1
        k += 1

    # j가 아직 안끝났을 경우
    while j <= right:
        temp[k] = seq[j]
        j += 1
        k += 1

    # 정렬된 temp를 원래 리스트로 복제
    for t in range(left, right + 1):
        seq[t] = temp[t]

    #print(seq)

병합 정렬(Merge Sort)은 비슷한 분할정복방식인 퀵 정렬에 비해 시간은 더 많이 소요되지만,
안정적인 정렬방식이라는 장점이 있습니다.