[알고리즘 / 정렬] 병합정렬(merge sort) / 파이썬코드

병합정렬이란

합병정렬이라고도 불리는 병합정렬(merge sort)는 존 폰 노이만이 1945년도에 개발한 분할 정복을 기반으로 하는 정렬 알고리즘이다. 

 

작동원리

1. 분할 (divide)

하나의 요소만을 가질때까지 입력 배열을 반으로 계속 분할한다. 

 

2. 정복(conquer), 결합(merge)

2개의 하위배열을 정렬하며 병합하고 최종적으로 정렬된 배열을 완성한다. 

 

시간복잡도

최선, 평균, 최악의 경우 O(n log n)

 

배열을 반으로 분할할때 log n 시간이 걸리고 

각 레벨에서 n개의 요소를 비교하기때문

공간복잡도

O(n)

 

장단점

장점

최악의 경우에도 O(n log n)의 시간복잡도인 안정적인 정렬방법이다.

큰 데이터에 효율적이다. 

 

단점

추가적인 메모리가 필요하다 (in-place 정렬이 아니다)

가장 빠른 정렬 방법은 아니다. 

---

Python 병합정렬 코드 (python merge sort)

# 병합정렬

def marge(start, end, mid):
    ### 병합 부분 ### 
    for i in range(start, end + 1):
        temp[i] = datalist[i]
    
    k = start
    index1 = start # 그룹 1
    index2 = mid + 1 # 그룹 2
    
    while index1 <= mid and index2 <= end: # index1, 2가 자신 그룹에 속해있을때
        if temp[index1] > temp[index2]: # 2번그룹(뒤 그룹)이 더 크면  
            datalist[k] = temp[index2]
            k += 1
            index2 += 1
        else:
            datalist[k] = temp[index1]
            k += 1
            index1 += 1
    # 위 반복문에서 한쪽 그룹은 완전히 정리될텐데,
    # 남은 나머지 그룹정리
    while index1 <= mid: 
        datalist[k] = temp[index1]
        k += 1
        index1 += 1
    while index2 <= end:
        datalist[k] = temp[index2]
        k+=1
        index2 += 1
    ### 병합 부분 끝 ###
    
def merge_sort(start, end):
    if end - start < 1: # 요소 1개 이하로 분활되면 리턴
        return
    mid = start + ((end - start) // 2) # 중간(start <-> end) 정의 
    merge_sort(start, mid) #분활
    merge_sort(mid + 1, end) #분활
    marge(start, end, mid)
    
    
N = int(input())
datalist = [0] * (N + 1)
temp = [0] * (N + 1)

for i in range(1, N + 1):
    datalist[i] = int(input())
    
merge_sort(1, N)

# print(*datalist)

for i in range(1, N + 1):
    print(datalist[i])

 

 

# 병합정렬


def merge_sort(start, end):
    if end - start < 1: # 요소 1개 이하로 분활되면 리턴
        return
    # 아래처럼 중간값 구하면 미미하지만 오버플로우에 좀 더 안전 (파이썬은 상관 X)
    mid = start + ((end - start) // 2) # 중간(start <-> end) 정의 
    merge_sort(start, mid) #분활
    merge_sort(mid + 1, end) #분활
    
    ### 병합 부분 ### 
    for i in range(start, end + 1):
        temp[i] = datalist[i]
    
    k = start
    index1 = start # 그룹 1
    index2 = mid + 1 # 그룹 2
    
    while index1 <= mid and index2 <= end: # index1, 2가 자신 그룹에 속해있을때
        if temp[index1] > temp[index2]: # 2번그룹(뒤 그룹)이 더 크면  
            datalist[k] = temp[index2]
            k += 1
            index2 += 1
        else:
            datalist[k] = temp[index1]
            k += 1
            index1 += 1
    # 위 반복문에서 한쪽 그룹은 완전히 정리될텐데,
    # 남은 나머지 그룹정리
    while index1 <= mid: 
        datalist[k] = temp[index1]
        k += 1
        index1 += 1
    while index2 <= end:
        datalist[k] = temp[index2]
        k+=1
        index2 += 1
    ### 병합 부분 끝 ###
    
N = int(input())
datalist = [0] * (N + 1)
temp = [0] * (N + 1)

for i in range(1, N + 1):
    datalist[i] = int(input())
    
merge_sort(1, N)

# print(*datalist)

for i in range(1, N + 1):
    print(datalist[i])

 

 

2개가 알고리즘은 같은 코드이니 편한 코드로 보시면 됩니다. 

 

2024년 새해 복 많이 받으세요