정렬 - 5) 병합 정렬 (merge sort)

 

📍 병합 정렬: 반으로 나눠서 정렬하는, 더 빠른 정렬

• 1) 배열의 길이가 1개가 될 때까지 재귀적으로 쪼개기 → O(logN)
• 2) 쪼갠 배열을 합쳐가며 정렬된 배열로 만들기 → O(N)
• 분할 정복 (Divide and Conquer)
• 시간복잡도: O(NlogN)

---

 

---

 

💬 python 코드 

• n 개의 원소가 주어졌을 때, 병합 정렬을 이용해 n 개의 숫자를 오름차순으로 정렬 

n = int(input())
arr = list(map(int, input().split()))
merged_arr = [0] * n


def merge(low, mid, high):
    i = low; j = mid + 1
    k = low

    while i <= mid and j <= high:
        if arr[i] <= arr[j]: # 첫번째 원소가 더 작다면
            merged_arr[k] = arr[i]
            k += 1
            i += 1
        else: # 두번째 원소가 더 작다면
            merged_arr[k] = arr[j]
            k += 1
            j += 1
    
    while i <= mid: # 아직 첫번째 리스트 내 원소가 남아있다면 
        merged_arr[k] = arr[i] # 남은 원소 모두 옮겨주기
        k += 1
        i += 1

    while j <= high: # 아직 두번째 리스트 내 원소가 남아 있다면
        merged_arr[k] = arr[j] # 남은 원소 모두 옮겨주기
        k += 1
        j += 1
    
    for k in range(low, high+1): # 병합된 리스트를 다시 원본 리스트에 옮겨주기
        arr[k] = merged_arr[k]

    return arr


def merge_sort(low, high): 
    if low < high:
        mid = (low + high) // 2  # 원소가 두 개 이상인 경우, 반으로 나눔
        merge_sort(low, mid) # 재귀적 정렬 
        merge_sort(mid+1, high) # 재귀적 정렬

        merge(low, mid, high) # 두 리스트 합치기

merge_sort(0, n-1)

print(*arr)