병합 정렬

배열을 절반으로 재귀적으로 분할한 뒤, 정렬된 두 배열을 합치며(merge) 정렬하는 분할 정복 알고리즘입니다.

동작 과정

[5, 3, 8, 1, 2]

분할:
[5, 3, 8, 1, 2]
→ [5, 3] / [8, 1, 2]
→ [5][3] / [8][1, 2]
→ [5][3] / [8][1][2]

병합:
[5][3]   → [3, 5]
[1][2]   → [1, 2]
[8][1,2] → [1, 2, 8]
[3,5][1,2,8] → [1, 2, 3, 5, 8]

구현

void mergeSort(int[] arr, int left, int right) {
    if (left >= right) return;
    int mid = (left + right) / 2;
    mergeSort(arr, left, mid);
    mergeSort(arr, mid + 1, right);
    merge(arr, left, mid, right);
}

void merge(int[] arr, int left, int mid, int right) {
    int[] tmp = Arrays.copyOfRange(arr, left, right + 1);
    int i = 0, j = mid - left + 1, k = left;
    while (i <= mid - left && j <= right - left) {
        if (tmp[i] <= tmp[j]) arr[k++] = tmp[i++];
        else                  arr[k++] = tmp[j++];
    }
    while (i <= mid - left) arr[k++] = tmp[i++];
    while (j <= right - left) arr[k++] = tmp[j++];
}

복잡도

• 안정 정렬 O
• out-of-place — 보조 배열 필요
• 연결 리스트 정렬에 유리 (포인터만 바꾸면 됨)

→ 정렬