병합 정렬 (Merge Sort)

병합 정렬 알고리즘의 기본 개념

 

• 존 폰 노이만 이라는 사람이 제안한 방법
• 일반적인 방법으로 구현했을 때 이 정렬은 안정 정렬에 속하며, 분할 정복 알고리즘의 하나이다.
  • 분할 정복 방법
    • 문제를 작은 2개의 문제로 분리하고 각각을 해결한 다음, 결과를 모아서 원래의 문제를 해결하는 전략.
    • 분할 정복 방법은 대게 재귀적 호출을 이용하여 구현한다.
• 알고리즘의 과정
  1. 리스트의 길이가 0 또는 1이면 이미 정렬된 것으로 본다.
  2. 그렇지 않은 경우 정렬되지 않은 리스트를 절반으로 잘라 비슷한 크기의 두 부분 리스트로 나눈다.
  3. 각 부분 리스트를 재귀적으로 병합 정렬을 이용해 정렬한다.
  4. 두 부분 리스트를 다시 하나의 정렬된 리스트로 병합한다.

파이썬으로 코드 구현

 

코드 구현

def mergesort(list):
    if len(list) <= 1:   # 배열의 길이가 1 이하면 리스트 배열
        return list
    
    mid = len(list)//2   # 리스트를 2등분한뒤 재귀 호출을 통해 왼쪽 배열과 오른쪽 배열을 정렬한다. 
    left = mergesort(list[:mid])
    right = mergesort(list[mid:])
    return merge(left, right)  # 정렬되어있는 왼쪽 배열과 오른쪽 배열을 병합한다.

def merge(left, right):
    result = []
    left_ = 0
    right_ = 0

    # 양쪽 배열의 값들을 비교하면서 작은값을 결과에 추가해 나간다.
    while left_ < len(left) and right_ < len(right): 
        if left[left_] <= right[right_]:
            result.append(left[left_])
            left_ += 1
        else:
            result.append(right[right_])
            right_ += 1

    result += left[left_:]
    result += right[right_:]
    return result

 

알고리즘 테스트 1

test = [14, 2, 644, 65, 12, 99, 9, 34, 23, 65]
print(mergesort(test))

 

결과

[2, 9, 12, 14, 23, 34, 65, 65, 99, 644]

 

알고리즘 테스트 2

 

아래의 네가지 데이터를 넣고 테스트도 진행해 보았다.

1. 정렬이 끝난 배열
2. 역순으로 정렬된 배열
3. 원소가 전부 같은 배열
4. 랜덤으로 구성된 배열

import time

def mergesort(list):
    if len(list) <= 1:
        return list
    
    mid = len(list)//2
    left = mergesort(list[:mid])
    right = mergesort(list[mid:])
    return merge(left, right)

def merge(left, right):
    result = []
    left_ = 0
    right_ = 0

    while left_ < len(left) and right_ < len(right):
        if left[left_] <= right[right_]:
            result.append(left[left_])
            left_ += 1
        else:
            result.append(right[right_])
            right_ += 1

    result += left[left_:]
    result += right[right_:]
    return result

test1 = [1, 2, 3, 4, 5, 6, 7]
test2 = [7, 6, 5, 4, 3, 2, 1]
test3 = [1, 1, 1, 1, 1, 1, 1, 1]
test4 = [23, 15, 38, 94, 62, 123, 243, 234, 112]

start_time1 = time.time()
mergesort(test1)
end_time1 = time.time()
total_time1 = (end_time1 - start_time1) * 1000

start_time2 = time.time()
mergesort(test2)
end_time2 = time.time()
total_time2 = (end_time2 - start_time2) * 1000

start_time3 = time.time()
mergesort(test3)
end_time3 = time.time()
total_time3 = (end_time3 - start_time3) * 1000

start_time4 = time.time()
mergesort(test4)
end_time4 = time.time()
total_time4 = (end_time4 - start_time4) * 1000

print(f'{total_time1:.4f}ms')
print(f'{total_time2:.4f}ms')
print(f'{total_time3:.4f}ms')
print(f'{total_time4:.4f}ms')

 

결과

0.0923ms
0.0865ms
0.0889ms
0.0880ms

병합정렬의 장단점

• 장점
  • 안정적인 성능 보장 : 최선, 최악, 평균 모든 경우에서 시간 복잡도가 O(nlogn)으로 일정하다.
  • 안정 정렬(Stable Sort) : 정렬 후에도 값이 같은 데이터들의 원래 순서가 유지된다.
  • 연결 리스트(Linked List) 정렬에 최적화 : 데이터 이동이 많은 연결 리스트를 정렬할 때 퀵 정렬 대비 효율이 높다.
• 단점
  • 추가 메모리 공간 필요 : 데이터를 합치는 과정에서 임시 배열이 필요하므로 공간 복잡도가 O(n)이다. 데이터가 아주 크면 메모리 낭비가 심해질 수 있다.
  • 제자리 정렬 불가 : 메모리를 추가로 사용하지 않는 정렬 알고리즘에 비해 상대적으로 비효율적일 수 있다.