[알고리즘] 병합(합병) 정렬(Merge Sort)

병합 정렬(Merge Sort)

병합 정렬은 분할 정복 알고리즘의 하나로 합병 정렬이라고도 한다. 불안정 정렬인 퀵 정렬과 달리, 병합 정렬은 안정 정렬에 속한다. 전체 데이터를 가장 작은 단위로 분할한 후 분할한 데이터를 다시 병합하면서 정렬하는 재귀용법을 활용한 정렬 알고리즘이다.

퀵 정렬과 비교했을 때, 차이점은 아래와 같다.

• 퀵 정렬
  - 각 요소를 피벗과 비교하여 요소를 정렬
  - 피벗을 통해 정렬(partition) → 영역을 쪼갬(quick sort)
• 병합 정렬
  - 배열을 하나의 요소가 남을 때까지 두 개의 하위 배열 (n / 2)로 반복하여 나눔
  - 영역을 쪼갤 수 있을 만큼 쪼갬(merge sort) → 정렬(merge)

 

 

 

정렬 과정

1. 분할(Divide) 단계
   리스트를 절반으로 나누어 비슷한 크기의 두 부분 리스트로 나눔
2. 정복(Conquer) 단계
   부분 리스트를 정렬함. 부분 리스트의 크기가 충분히 작지 않으면 순환 호출을 이용해 다시 분할 정복 방법을 적용
3. 결합(Combine) 단계
   정렬된 부분 리스트들을 하나의 배열에 병합

출처 : https://medium.com/@bill.shantang/8-classical-sorting-algorithms-d048eec3fdab

출처 : https://gmlwjd9405.github.io/2018/05/08/algorithm-merge-sort.html

 

 

 

파이썬 코드

def merge_sort(arr):
    if len(arr) <= 1:  # 더이상 분할 불가
        return arr

    mid = len(arr) // 2

    # 재귀 호출로 분할 : Divide
    left = merge_sort(arr[:mid])
    right = merge_sort(arr[mid:])

    return merge(left, right)


def merge(left, right):
    sorted_list = []

    # 나눠진 두 배열을 정렬 : Conquer
    while 0 < len(left) and 0 < len(right):
        if left[0] <= right[0]:
            sorted_list.append(left.pop(0))
        else:
            sorted_list.append(right.pop(0))

    # 비교후 남아있는 값 병합 : Merge
    sorted_list.extend(left + right)

    return sorted_list

print(merge_sort([5, 3, 8, -1, 9, 2]))

혹은

# 위에 있던 merge 함수에서 수행하는 기능을
# merge_sort 함수에 모두 포함시킨 버전
def merge_sort(arr):
    if len(arr) <= 1:
        return arr
    mid = len(arr) // 2

    left = merge_sort(arr[:mid])
    right = merge_sort(arr[mid:])

    sorted_list = []
    while 0 < len(left) and 0 < len(right):
        if left[0] <= right[0]:
            sorted_list.append(left.pop(0))
        else:
            sorted_list.append(right.pop(0))

    sorted_list.extend(left + right)

    return sorted_list

 

 

 

 

 

https://western-sky.tistory.com/22

[병합 정렬] Merge Sort - Python

https://gmlwjd9405.github.io/2018/05/08/algorithm-merge-sort.html

[알고리즘] 합병 정렬(merge sort)이란 - Heee's Development Blog

https://ko.strephonsays.com/what-is-the-difference-between-quicksort-and-merge-sort

https://data-marketing-bk.tistory.com/31

고급정렬1. 병합정렬(Merge Sort) 완벽 마스터하기