Merge Sort 완전 가이드: 분할 정복 알고리즘

Source: Dev.to

소개

Merge Sort는 Divide y Vencerás 패러다임을 기반으로 하는 정렬 알고리즘입니다. 배열을 재귀적으로 절반으로 나누어 개별 요소(정의상 정렬된)까지 분할한 다음, 이를 정렬된 형태로 병합합니다. 모든 경우에 O(n log n) 성능을 보장합니다.

이 알고리즘(또는 Ordenamiento por Mezcla이라고도 함)은 컴퓨터 과학에서 정렬의 핵심 중 하나입니다. 안정성과 보장된 성능이 필요할 때 특히 돋보입니다.

알고리즘 단계

1. Divide
   배열을 재귀적으로 반으로 나누어 개별 요소에 도달할 때까지 진행하며, 이 요소들은 이미 정렬된 것으로 간주됩니다.

2. Conquista (Conquer)
   각 하위 구분을 독립적으로 해결하고 정렬합니다.

3. Combina (Merge)
   two‑pointers 기법을 사용해 조각들을 합치거나 “섞어” 결과 조합이 계속 정렬된 상태를 유지하도록 합니다.

인기 있는 QuickSort와 달리 Merge Sort는 모든 상황(최선, 평균, 최악)에서 실행 시간 복잡도가 **O(n log n)**임을 항상 보장합니다. 그러나 이러한 일정한 성능은 메모리(RAM) 사용량이 더 많이 소요된다는 비용이 따릅니다.

Go에서 가독성 좋은 구현

func sortList(unsortedList []int) []int {
    n := len(unsortedList)
    if n <= 1 {
        return unsortedList
    }

    midpoint := n / 2
    leftList := sortList(unsortedList[:midpoint])
    rightList := sortList(unsortedList[midpoint:])

    resultList := make([]int, 0, n)
    leftPointer, rightPointer := 0, 0

    for leftPointer < midpoint || rightPointer < n-midpoint {
        if leftPointer == midpoint {
            resultList = append(resultList, rightList[rightPointer])
            rightPointer++
        } else if rightPointer == n-midpoint {
            resultList = append(resultList, leftList[leftPointer])
            leftPointer++
        } else if leftList[leftPointer] <= rightList[rightPointer] {
            resultList = append(resultList, leftList[leftPointer])
            leftPointer++
        } else {
            resultList = append(resultList, rightList[rightPointer])
            rightPointer++
        }
    }
    return resultList
}

이 버전은 명확하고 디버깅하기 쉽지만, 재귀 호출마다 새로운 slice를 생성하므로 동적 메모리 할당과 garbage collector에 대한 부담이 발생합니다.

공유 버퍼 패턴을 이용한 최적화

고규모 환경이나 표준 라이브러리에서는 재귀 전체에 걸쳐 재사용되는 단일 보조 버퍼를 할당하는 것이 바람직합니다.

func SortList(arr []int) []int {
    if len(arr) <= 1 {
        return arr
    }

    // Un solo buffer auxiliar compartido para toda la ejecución
    temp := make([]int, len(arr))
    mergeSort(arr, temp, 0, len(arr)-1)
    return arr
}

func mergeSort(arr, temp []int, left, right int) {
    if left < right {
        mid := left + (right-left)/2

        mergeSort(arr, temp, left, mid)
        mergeSort(arr, temp, mid+1, right)

        merge(arr, temp, left, mid, right)
    }
}

func merge(arr, temp []int, left, mid, right int) {
    // Copiar el segmento actual al buffer temporal
    for i := left; i <= right; i++ {
        temp[i] = arr[i]
    }

    i, j, k := left, mid+1, left

    // Fusionar de nuevo en el arreglo original
    for i <= mid && j <= right {
        if temp[i] <= temp[j] {
            arr[k] = temp[i]
            i++
        } else {
            arr[k] = temp[j]
            j++
        }
        k++
    }

    // Copiar los elementos restantes del sub‑arreglo izquierdo (si los hay)
    for i <= mid {
        arr[k] = temp[i]
        i++
        k++
    }
}

이 접근법을 사용하면 추가 메모리가 O(N) 로 엄격히 유지됩니다; 병합이나 분할이 몇 번 발생하든 버퍼의 원래 크기를 초과하지 않습니다.

결론

Merge Sort는 수학적 견고함과 실행 시간의 안정적인 동작으로 돋보입니다. 메모리 사용량 때문에 개발자들이 QuickSort를 선호하는 경우가 많지만, Shared Buffer Pattern과 같은 기술은 오버헤드를 크게 줄여 Merge Sort를 다시 주요 위치로 되돌립니다, 특히 다음과 같은 경우에:

• 순차 접근이 자연스러운 연결 리스트 정렬.
• 대규모에서 안정성과 보장된 성능을 요구하는 애플리케이션.