[Algorithm] 병합 정렬

※ 병합 정렬이란?

 

 

병합 정렬은 분할 정복 알고리즘 중 하나이며, 반으로 분할하여 정렬을 한 후 병합을 진행한다.

 

---

 

다음 데이터 셋을 병합 정렬로 정렬해보자.

 

 

[7,5,4,3,5,8,9,10]

 

1. 원소가 하나씩 남을 때까지 데이터 셋을 쪼갠다. 

7 / 5 / 4 / 3 / 5 / 8 / 9 / 10

2. 2개씩 짝지어 정렬을 진행한 후 병합한다.

5 7 / 3 4 → 3 4 5 7

5 8 / 9 10 → 5 8 9 10

3. 두 데이터 셋을 정렬하여 병합한다.

[ 3 4 5 5 7 8 9 10 ]

 

 

 

병합 정렬을 Python으로 구현한 코드는 다음과 같다.

 

[ Python Code 👩🏻‍💻]

 

data_set = [7,5,4,3,5,8,9,10]
merge_data = [0]*len(data_set)
d = []

def merge(data,m,middle,n):
    i = m
    j = middle+1
    k = m
    
    while(i <= middle and j <=n):
        if(data[i]<=data[j]):
            merge_data[k] = data[i]
            i +=1
        else :
            merge_data[k] = data[j]
            j +=1
        k +=1
        
    if(i > middle):
        for t in range(j,n+1):
            merge_data[k] = data[t]
            k +=1
            
    else :
        for t in range(i,middle+1):
            merge_data[k] = data[t]
            k +=1
                
    for i in range(m,n+1):
        data[i] = merge_data[i]
            
            
            
def mergesort(data,m,n):
    if(m < n):
        middle = int((m+n)/2)
        mergesort(data,m,middle)
        mergesort(data,middle+1,n)
        merge(data,m,middle,n)
    

mergesort(data_set,0,len(data_set)-1)
print(data_set)

 

 

병합 정렬의 시간 복잡도는?

 

병합 정렬은 분할하여 정렬을 진행한다는 점에서 데이터 개수가 N개일 때, O(N*logN)의 시간 복잡도를 보장합니다. 병합 정렬은 기존의 데이터를 담은 추가적인 공간이 필요하다는 점에서 메모리 활용이 비효율적이며, 대체로 퀵 정렬보다 빠르지 않지만 O(N*logN)의 시간복잡도를 보장한다는 점에서는 효율적이다.