[알고리즘 기초] 병합 정렬 Merge Sort

병합 정렬(merge sort)은 입력된 요소들의 리스트를 정렬하는데 사용되는 인기있고 효율적인 정렬 알고리즘입니다. 이 알고리즘은 분할 정복(divide-and-conquer) 접근 방식을 사용하여 입력 리스트를 두 부분으로 나누고, 각 부분을 재귀적으로 정렬한 후, 정렬된 두 부분을 다시 병합하여 최종적으로 정렬된 리스트를 생성합니다. 이 알고리즘의 핵심 아이디어는 리스트를 반복적으로 더 작은 부분으로 분할하고 각각을 개별적으로 정렬한 후 정렬된 순서로 결합하는 것입니다.

다음은 병합 정렬 알고리즘의 단계별 설명입니다:

1. 정렬되지 않은 리스트를 두 부분으로 나눕니다: 이 단계에서 원래 리스트를 두 개의 거의 동일한 크기의 하위 리스트로 나눕니다. 리스트에 하나 또는 아무런 요소도 없다면 이미 정렬된 것으로 간주합니다.

2. 각 하위 리스트를 재귀적으로 정렬합니다: 이전 단계에서 생성된 두 개의 작은 하위 리스트를 머지 소트 알고리즘을 사용하여 재귀적으로 정렬합니다. 이 재귀적인 정렬은 하위 리스트가 하나 또는 아무런 요소도 없을 때까지 계속됩니다.

3. 정렬된 하위 리스트들을 병합합니다: 모든 하위 리스트가 정렬되면 알고리즘은 이들을 병합하여 하나의 정렬된 리스트로 만듭니다. 이 병합 과정에서 두 하위 리스트의 요소들을 비교하고 정렬된 순서로 최종 리스트에 추가합니다.

머지 소트 알고리즘은 O(n log n)의 시간 복잡도를 갖기 때문에 큰 리스트에 대해 효율적으로 작동합니다. 이 알고리즘은 안정적인 정렬 방법으로서 동일한 값의 상대적 순서를 유지합니다. 또한 하위 리스트를 병합하는 데 추가적인 메모리(일반적으로 보조 배열)를 필요로 합니다.

def mergeSort(ns):
    if len(ns) < 2:
        return ns

    # recursion
    leftNums = mergeSort(ns[:len(ns) // 2])
    rightNums = mergeSort(ns[len(ns) // 2:])

    # merge
    mergedNums = []
    leftIdx, rightIdx = 0, 0
    while leftIdx < len(leftNums) and rightIdx < len(rightNums):
        if leftNums[leftIdx] < rightNums[rightIdx]:
            mergedNums.append(leftNums[leftIdx])
            leftIdx += 1
        else:
			rightNums[rightIdx]
            mergedNums.append(rightNums[rightIdx])
            rightIdx += 1


    mergedNums += leftNums[leftIdx:]
    mergedNums += rightNums[rightIdx:]

    return mergedNums


nums = [8, 1, 4, 3, 2, 5, 10, 6]
print(f'mergedNums: {mergeSort(nums)}')

위 코드를 응용하여, 입력인수에 따라 숫자를 내림차순으로 정렬하는 알고리즘도 구현할 수 있습니다.

import random
import copy


def mergeSort(ns, asc=True):
    nums = copy.copy(ns)
    if len(nums) < 2:
        return nums

    leftNums = mergeSort(nums[:len(nums)//2], asc=asc)   # 일관성 있게 초기에 입력된 'asc'를 인수로 받아야 함
    rightNums = mergeSort(nums[len(nums)//2:], asc=asc)   # 일관성 있게 초기에 입력된 'asc'를 인수로 받아야 함

    mergedNums = []
    leftIdx, rightIdx = 0, 0
    while leftIdx < len(leftNums) and rightIdx < len(rightNums):
        if asc:
            if leftNums[leftIdx] < rightNums[rightIdx]:
                mergedNums.append(leftNums[leftIdx])
                leftIdx += 1
            else:
                mergedNums.append(rightNums[rightIdx])
                rightIdx += 1
        else:    # 비교 연산자 반대로 넣어주기
            if leftNums[leftIdx] > rightNums[rightIdx]:
                mergedNums.append(leftNums[leftIdx])
                leftIdx += 1
            else:
                mergedNums.append(rightNums[rightIdx])
                rightIdx += 1

    mergedNums += leftNums[leftIdx:]  # add leftovers
    mergedNums += rightNums[rightIdx:]  # add leftovers
    return mergedNums


rNums = random.sample(range(101), 10)
print(f'not sorted rNums: {rNums}')
print(f'ascending rNums: {mergeSort(rNums)}')
print(f'descending rNums: {mergeSort(rNums, asc=False)}')