합병 정렬 (Merge Sort)

합병 정렬

: 배열을 좌 우로 나눈 후, 나눈 배열을 정렬하고 다시 붙인다. 퀵 정렬(Quick Sort)과 마찬가지로 재귀 용법을 활용하는 알고리즘이다. 분할 정복 알고리즘 중 하나로, 리스트 길이가 1 이하면 이미 정렬된 것으로 본다.

 

1. 분할 : 정렬되지 않은 리스트를 절반으로 잘라 비슷한 크기의 두 리스트로 만든다.
2. 정복 : 각 부분 리스트를 재귀적으로 합병 정렬을 이용해 정렬한다.
3. 결합 : 두 부분 리스트를 다시 하나의 정렬된 리스트로 합병한다. 이 때 정렬 결과가 임시 배열에 저장된다.
4. 복사 : 임시 배열에 저장된 결과를 원래 배열에 복사한다.

 

출처: https://en.wikipedia.org/wiki/Merge _sort

 

 

 

알게된 개념

 

1. 리스트 요소 끄집어내기(pop)

-> pop()은 리스트의 맨 마지막 요소를 돌려주고 그 요소는 삭제한다.

>>> a = [1,2,3]
>>> a.pop()
3
>>> a
[1, 2]

-> pop(x)는 리스트의 x번째 요소를 돌려주고 그 요소는 삭제한다.

>>> a = [1,2,3,4,5]
>>> a.pop(1)
2
>>> a
[1, 3, 4, 5]

 

2. 리스트 확장(extend)

-> extend(x)에서 x에는 리스트만 올 수 있으며 원래의 a 리스트에 x 리스트를 더하게 된다.

>>> x = [1,2,3,4,5]
>>> x.extend([6,7])
>>> 7
[1, 2, 3, 4, 5, 6, 7]
>>> y = [8, 9]
>>> x.extend(y)
>>> x
[1, 2, 3, 4, 5, 6, 7, 8, 9]

x.extend([6,7]]은 x += [6,7]과 동일하다!!!

 

 

 

 

파이썬으로 구현한 합병 정렬

def merge_sort(arr):
    if len(arr) <= 1:
        return arr
    
    # divde 과정
    mid = len(arr) // 2
    left = arr[:mid]
    right = arr[mid:]

    # list의 길이가 1이 될 때까지 divide
    left = merge_sort(left)
    right = merge_sort(right)

    return merge(left, right)

def merge(left, right):
    # 복사할 임시 배열
    copy = []

    # 양쪽 두 리스트 중 하나라도 원소가 없을 때까지 반복.
    while left and right:
        if left[0] < right[0]:
            copy.append(left.pop(0))
        else:
            copy.append(right.pop(0))

    # 만약 왼쪽 혹은 오른쪽 리스트가 남았을 때 모두 다 집어넣기
    if left:
        copy.extend(left)
    elif right:
        copy.extend(right)
    
    return copy

arr = [5, 2, 3, 9, 6, 1, 8, 4, 7]
print(merge_sort(arr))