병합 정렬 알고리즘

요소를 낱개로 다 쪼갠 뒤 쪼갠 것을 비교해가며 합치는 방식

합칠 때는 다음 과정을 따른다.

 

1. 2덩어리씩  합침. 이때 정렬해서 합침

2. 2덩어리(a, b) 와 하나로 합쳐질 덩어리(c) 3개에서 각각 index 역할을 해줄 변수들을 3개 만듦

3. index를 활용해 a, b를 비교하고 작은 것을 c에 추가하며 index들을 1씩 증가시키는 것을 반복

4. a, b 한 쪽을 다 채워넣었다면 나머지 한 쪽은 그냥 순차적으로 채워넣으면 됨(a, b모두 이미 반복되는 과정에서 정렬이 보장된 것들임)

def merge_sort(array):
# 1개가 될 때까지 재귀적으로 쪼갬
    if len(array) <= 1:
        return array

    mid = len(array) // 2
    left = merge_sort(array[:mid])
    right = merge_sort(array[mid:])

# 왼쪽, 오른쪽 모두 남았을 경우
    i, j, k = 0, 0, 0
    while len(left) > i and len(right) > j:
        if left[i] > right[j]:
            array[k] = left[i]
            i += 1
        else:
            array[k] = right[j]
            j += 1
        k += 1

# 왼쪽, 오른쪽 한 쪽을 먼저 다 채워넣었을 경우
    while len(left) > i:
        array[k] = left[i]
        k += 1
        i += 1
    while len(right) > j:
        array[k] = right[j]
        k += 1
        j += 1

    return array