[알고리즘] 병합 정렬 (merge sort)

병합(머지) 정렬

배열을 앞부분과 뒷부분의 두 그룹으로 나누어 각각 정렬한 후 병합하는 작업을 반복하는 알고리즘이다.

• 분할(리스트의 크기가 1이 될 때까지)과 정복(리스트를 정렬된 상태로 병합)
• 쪼갤 때는 한 개까지!
• 병합 할 때에는 정렬이 된 두 개의 배열을 계속해서 병합!
• stable 안정적이다.
• 대규모 데이터를 정렬할 때, 안정적인 성능이 요구되는 상황에서 많이 사용된다.

시간복잡도

O(n logn) = 배열 병합의 시간 복잡도 O(n) x 데이터 원소 수가 n일 때 병합 정렬의 단계는 log n만큼 필요 O(log n) = O(n) x O(log n)

두 개(a,b)의 배열을 한 개(c)의 배열로 병합 해보기!

a=[2,4,6,8,11,13]
b=[1,2,3,4,9,16,21]
c=[None]*(len(a)+len(b))

pa, pb, pc = 0, 0, 0 # 각 배열의 커서
na, nb, nc = len(a), len(b), len(c) # 각 배열의 원소의 수  

while pa<na and pb <nb: # 배열의 커서가 인덱스 번호를 넘지 않을 때까지
    if a[pa] <= b[pb]: # b에 커서의 인덱스가 a의 커서보다 크거나 같을 때
        c[pc] = a[pa] # c 배열에 작은 값 a[pa] 삽입
        pa += 1 # pa 커서 값 증가
    else:
        # b에 커서 위치의 값이 a커서 위치의 값보다 작을 때
        c[pc] = b[pb]
        pb+=1
    pc+=1

while pa < na: # a에 남은 원소가 있을 때
    c[pc] = a[pa] # c에 복사
    pa+=1
    pc+=1

while pb < nb : # b에 남은 원소가 있을 때
    c[pc] = b[pb]
    pb+=1
    pc+=1
print(c)

(참고) sorted() 함수로 병합 정렬하기

a = [2,4,6,8,11,13]
b = [1,2,3,4,9,16,21]

# sorted 사용 병합 (정렬 되어 있지 않아도 되지만 속도가 빠르지 않다.)
c=list(sorted(a+b)) # a와 b를 연결하여 오름차순으로 정렬한 것을 list로

# 정렬을 마친 두 배열의 병합(heapq.merge 사용)
import heapq
c=list(heapq.merge(a,b)) # a,b 병합

병합 정렬 만들기

정렬을 마친 배열의 병합을 응용하여 _분할 정복법_에 따라 정렬하는 알고리즘이 병합 정렬이다.

• 12개 -> 6개 -> 3개 ... 계속 해서 쪼갠다 이 후 병합하며 정렬한다. 쪼개고 병합하며 정렬하는 알고리즘이다
• 병합 정렬 알고리즘의 순서(배열의 원소 수가 2개 이상인 경우)
  1. 배열의 앞부분을 병합 정렬로 정렬한다.
  2. 배열의 뒷부분을 병합 정렬로 정렬한다.
  3. 배열의 앞부분과 뒷부분을 병합한다.

병합 정렬 알고리즘 구현해보자!

# GPT 형님의 코드, 가독성이 더 좋다.
def merge_sort(arr):
    # 배열의 길이가 1 이하이면 이미 정렬된 상태로 반환
    if len(arr) <= 1:
        return arr

    # 배열을 중간 기준으로 두 부분으로 분할
    mid = len(arr) // 2
    left_half = merge_sort(arr[:mid])
    right_half = merge_sort(arr[mid:]) 
    # 분할된 두 배열을 병합하여 반환
    return merge(left_half, right_half)

def merge(left, right):
    sorted_list = []
    i = j = 0
    # 두 리스트를 병합하는 과정
    while i < len(left) and j < len(right):
        if left[i] < right[j]:
            sorted_list.append(left[i])
            i += 1

        else:
            sorted_list.append(right[j])
            j += 1
    # 남아 있는 요소를 추가
    sorted_list.extend(left[i:])
    sorted_list.extend(right[j:])

    return sorted_list
# 예시
arr = [38, 27, 43, 3, 9, 82, 10]
sorted_arr = merge_sort(arr)
print("정렬된 배열:", sorted_arr)

다른 방법

# 책 내용의 코드
a=[5,8,4,2,6,1,3,9,7]
n = len(a)
buff=[None]*n 

def merge_sort(a,left,right):
    # 파라미터 값의 의미
    # a : 병합 정렬할 배열
    # left : 배열의 맨 왼쪽 index
    # right : 배열의 맨 오른쪽 index
    if left < right:
        center = (left+right)//2
        merge_sort(a,left,center) # 재귀호출로 앞부분 정렬
        merge_sort(a,center+1,right) # 재귀호출로 뒷부분 정렬
        p=j=0
        i=k=left

        while i <= center:
            buff[p]=a[i]
            p+=1
            i+=1

        while i <= right and j<p:
            if buff[j] <= a[i]:
                a[k] = buff[j]
                j+=1
            else:
                a[k]=a[i]
                i+=1
            k+=1

        while j<p:
            a[k] = buff[j]
            k+=1
            j+=1

merge_sort(a,0,n-1)
print(a) # 정렬된 a 배