[알고리즘] Merge Sort

Merge Sort

Divide and Conquer(분할정복) 방법을 통해 구현

Pivot 없이 정확히 반씩 나누어 나중에 정렬하는 알고리즘

---

Process

1. 리스트 길이가 2 이상일 때 절반으로 분할한다 (divide)

2. 각 부분 리스트를 재귀적으로 합병 정렬을 이용해 정렬한다 (conquer)

3. 두 부분 리스트를 다시 하나의 정렬된 리스트로 합병하며, 정렬 결과를 임시배열에 저장한다 (combine)

4. 임시 배열에 저장된 결과를 원래 배열에 복사한다 (copy)

---

Code

numbers = []
length = 100


for i in range(length, 0, -1):
    numbers.append(i)


def merge(start, middle, end):
    temp = []

    i, j = start, middle + 1

    while i <= middle and j <= end:
        if numbers[i] < numbers[j]:
            temp.append(numbers[i])
            i += 1
        else:
            temp.append(numbers[j])
            j += 1

    while i <= middle:
        temp.append(numbers[i])
        i += 1

    while j <= end:
        temp.append(numbers[j])
        j += 1

    for idx in range(end - start + 1):
        numbers[start + idx] = temp[idx]


def mergeSort(start, end):
    if start >= end:
        return

    mid = (start + end) // 2

    mergeSort(start, mid)
    mergeSort(mid + 1, end)
    merge(start, mid, end)


mergeSort(0, length - 1)
print(numbers)

---

Time Complexity

최선/최악 모두 분할이 절반씩 일어나기때문에

비교 시간복잡도는 O(log₂N), 각 순환 호출 단계의 비교 연산은 O(N)으로 O(Nlog₂N) 이다

---

Space Complexity

정렬 시 별도 메모리 공간이 필요하다 O(N) 

---

C, JAVA, PYTHON 의 표준 정렬 라이브러리는 Quick Sort, Merge Sort 의 아이디어를 채택한 하이브리드 방식의 정렬 알고리즘을 사용한다

divide and conquer 과정에서 같은 값을 가지는 데이터의 인덱스가 변경되지 않으므로 stable sorting 이다