정렬 알고리즘 - ③ 병합 정렬

병합 정렬

병합 정렬(Merge Sort) 은 효율적이고 안정적인 정렬 알고리즘 중 하나로, 분할 정복(Divide and Conquer) 방식을 사용한다.

쉽게 말하면, 배열을 계속 절반으로 나눈 뒤 정렬하면서 다시 합쳐가는 방식이다.

 

병합 정렬은 먼저 입력된 배열을 재귀적으로 두 개의 절반으로 나누고, 나누어진 배열들을 각각 정렬한 뒤, 마지막에 다시 병합(merge) 하여 최종적으로 정렬된 배열을 만든다.

---

병합 정렬의 동작 방식

 

1️⃣ Divide(분할)

배열을 더 이상 나눌 수 없을 때까지 계속 절반씩 나눈다 👉 배열의 크기가 1이 될 때까지 재귀적으로 분할한다

2️⃣ Conquer (정복)

나누어진 각 부분 배열을 정렬한다.
👉 원소가 1개인 배열은 이미 정렬된 상태이기 때문에 다시 정렬할 필요가 없다.

3️⃣ Merge (병합)

정렬된 부분 배열들을 크기를 비교하면서 다시 합친다. 이 과정에서 더 작은 값은 먼저 넣으면서 정렬된 상태를 유지하면서 병합한다.

---

병합 정렬의 시간 복잡도

병합 정렬은 입력 데이터의 상태에 크게 영향을 받지 않고 거의 일정한 성능을 보이는 정렬 알고리즘이다.

최선의 경우(Best Case) : O(nlogn)

: 배열이 이미 정렬되어 있거나 거의 정렬된 상태여도 O(n log n) 의 시간 복잡도를 가진다.

평균적인 경우 (Average Case) : O(nlogn)

: 배열이 랜덤하게 섞여 있는 일반적인 상황에서도 O(nlogn) 으로 동작한다.

최악의 경우 (Worst Case) : O(nlogn)

: 배열이 완전히 역순으로 정렬되어 있는 경우에도 O(n log n) 의 시간 복잡도를 유지한다.

---

병합 정렬의 공간 복잡도

병합 정렬은 정렬 과정에서 임시 배열(temporary array) 을 추가로 사용하기 때문에 추가적인 메모리 공간이 필요하다.

즉, 원본 배열을 바로 정렬하는 것이 아니라 정렬한 결과를 임시 공간에 저장하며 병합하는 방식이기 때문에 공간 복잡도가 O(n) 이 된다.

💻 구현

1.  mergeSort() 함수

def mergeSort(arr, size):

    arr_merge = [0] * size  # 기존 배열의 크기만큼의 임시 배열을 미리 만둔다 - 공간 복잡도 O(n)

    mergeUtil(arr, arr_merge, 0, size - 1)
    return arr # 정렬 완료된 배열을 return 

---

2. mergeUtil() : 배열을 반으로 쪼개는 함수

이 함수는 분할을 맡는 함수이다.  배열을 더 이상 나눌 수 없을 때까지 계속 반으로 분할한다

def mergeUtil(arr, arrMerge, left, right): 

    if left < right:  # 반으로 나누었을 때 원소의 개수가 아직 1개가 아닐 때 

        mid = (left + right) // 2 # 배열의 중간 인덱스 
mergeUtil(arr, arrMerge, left, mid) # 왼쪽 부분 먼저 재귀 호출하면서 배열을 계속 반으로 쪼갠다 
        mergeUtil(arr, arrMerge, mid + 1, right)  # 오른쪽 부분 역시 재귀 호출로 배열을 계속 분할 

        merge(arr, arrMerge, left, mid, right) # 쪼갰던 것을 다시 병합 

---

3. merge() : 다시 병합하면서 정렬하는 함수

배열을 다 쪼갠 후, 쪼개진 값들을 서로 비교하면서 정렬된 상태로 병합한다.

def merge(arr, arrMerge, left, mid, right):
    idx1 = left # 왼쪽 부분 시작 인덱스
    idx2 = mid + 1 # 오른쪽 부분 시작 인덱스
    idxM = left # 실제 정렬된 값을 넣을 위치 

    # 비교 전에 현재 구간을 임시 배열에 미리 복사해놓기 
    for i in range(left, right + 1):
        arrMerge[i] = arr[i]

    # 왼쪽과 오른쪽 값을 비교하면서 작은 값을 먼저 넣기 
    while idx1 <= mid and idx2 <= right:
    # 왼쪽 값이 더 작을 때 
        if arrMerge[idx1] < arrMerge[idx2]:
            arr[idxM] = arrMerge[idx1] # 작은 값을 원본 배열에 넣기
            idx1 += 1  # 왼쪽 포인터 오른쪽으로 한칸 이동 
        else: # 오른쪽값이 더 작으면 그 값을 넣기
            arr[idxM] = arrMerge[idx2]
            idx2 += 1  # 오른쪽 포인터도 한 칸 이동 
        idxM += 1 # 다음 저장 위치로 이동하기 

    # 남은 원소 뒤에 이어 붙이기 
    while idx1 <= mid:
        arr[idxM] = arrMerge[idx1]
        idx1 += 1
        idxM += 1 

실행

unsortedArr = [40, 30, 10, 20, 50]
print(mergeSort(unsortedArr, len(unsortedArr)))

실행 결과