Merge Sort

Q: 병합 정렬의 시간 복잡도는 무엇인가요?

병합 정렬은 항상 배열을 절반으로 나누기 때문에 최선, 평균, 최악의 경우 모두 `O(n log n)`입니다. 병합 버퍼를 위해 `O(n)`의 추가 공간을 사용합니다.

Q: quicksort 대신 병합 정렬을 쓰는 이유는 무엇인가요?

병합 정렬은 적대적인 입력에서도 `O(n log n)`을 보장하고 안정적인 반면, quicksort는 `O(n²)`으로 저하될 수 있습니다. 병합 정렬은 연결 리스트와 외부 정렬에서도 선호됩니다. 단점은 `O(n)`의 추가 메모리입니다.

Q: 병합 정렬과 quicksort의 차이는 무엇인가요?

둘 다 분할 정복 정렬이지만, quicksort는 피벗을 기준으로 분할하며 `O(log n)`의 스택 공간으로 제자리에서 정렬하고, 병합 정렬은 무조건 절반으로 나눈 뒤 `O(n)` 버퍼로 병합합니다. quicksort는 캐시 지역성 덕분에 실제로 대개 더 빠르지만, 병합 정렬은 보장된 `O(n log n)` 최악 성능을 가지며 안정적입니다.

Q: 실무에서 병합 정렬은 언제 써야 하나요?

보장된 `O(n log n)` 한계를 가진 안정 정렬이 필요할 때, 연결 리스트를 정렬할 때(임의 접근이 필요 없음), 또는 메모리에 담기 어려운 큰 데이터를 외부 정렬할 때 병합 정렬을 선택하세요. `O(n)`의 추가 공간이 필요하므로 메모리가 부족할 때는 피하세요.

Q: 병합 정렬은 제자리에서 정렬하나요?

아니요. 표준 병합 정렬은 두 절반을 병합하기 위해 `O(n)`의 임시 버퍼를 할당하므로 제자리 정렬이 아닙니다. 제자리 병합 변형도 있지만 복잡하고 더 느리거나 안정성을 잃기 때문에, 버퍼를 사용하는 버전이 일반적인 선택입니다.

마지막 업데이트 2026년 7월 1일

병합 정렬은 분할 정복 알고리즘입니다. 각 조각이 하나의 원소만 가질 때까지(그 상태는 자명하게 정렬됨) 배열을 재귀적으로 절반으로 나눈 뒤, 조각들을 순서대로 다시 병합합니다. 병합 단계에서는 두 개의 정렬된 부분 배열을 두 포인터로 훑으며, 항상 앞쪽의 더 작은 원소를 다음으로 복사합니다. 위의 재생을 눌러 배열이 병합을 거치며 다시 만들어지는 모습을 확인하세요.

항상 절반으로 나누기 때문에 병합 정렬은 모든 경우에 O(n log n) 시간에 동작합니다. 최악의 경우도 최선의 경우만큼 좋습니다. 그 대가로 임시 병합 버퍼에 O(n)의 추가 공간을 사용합니다.

시간 및 공간 복잡도

경우	복잡도	비고
최선의 경우	O(n log n)	항상 입력을 절반으로 나눔
평균의 경우	O(n log n)	무작위 순서
최악의 경우	O(n log n)	보장됨 - 나쁜 입력이 없음
공간	O(n)	병합을 위한 임시 버퍼
안정성	예	동점은 병합 중 왼쪽을 우선하여 처리

단계별 과정

단계	무슨 일이 일어나는가
1	구간에 원소가 0개 또는 1개면 이미 정렬된 상태입니다.
2	구간을 두 개의 절반으로 나눕니다.
3	왼쪽 절반을 병합 정렬로 재귀적으로 정렬합니다.
4	오른쪽 절반을 병합 정렬로 재귀적으로 정렬합니다.
5	정렬된 두 절반을 두 포인터로 병합합니다.

예제 풀이

[5, 2, 4, 1] 정렬하기:

패스	배열	동작
분할	`[5, 2] \| [4, 1]`	배열을 두 절반으로 나눔
분할	`[5] [2] \| [4] [1]`	각 조각이 단일 원소가 될 때까지 다시 나눔
병합	`[2, 5] \| [1, 4]`	`[5]`,`[2]`를 `[2, 5]`로, `[4]`,`[1]`을 `[1, 4]`로 병합
병합	`[1, 2, 4, 5]`	`[2, 5]`와 `[1, 4]`를 병합: `1`, 그다음 `2`, `4`, `5` 선택
완료	`[1, 2, 4, 5]`	배열이 완전히 정렬됨

병합 정렬을 사용할 때

사용할 때	피할 때
보장된 `O(n log n)` 최악 성능이 필요할 때	메모리가 부족하고 `O(n)` 추가 공간이 허용되지 않을 때
안정성이 중요할 때(같은 키가 순서를 유지)	삽입 정렬이 더 빠른 작은 배열을 정렬할 때
연결 리스트를 정렬할 때	제자리 정렬이 필수 요구 사항일 때
데이터가 RAM에 담기에 너무 클 때(외부 정렬)	캐시 지역성이 지배적이고 quicksort의 제자리 패스가 유리할 때

Merge Sort 코드

Python, JavaScript, Java, C++, C로 작성된 깔끔하고 실행 가능한 Merge Sort 구현입니다. 언어를 선택해 코드를 복사하거나 Coddy 플레이그라운드에서 바로 열어보세요.

Python로 구현한 Merge Sort 코드Python
1def merge_sort(a):2    if len(a) <= 1:3        return a4    mid = len(a) // 25    left = merge_sort(a[:mid])6    right = merge_sort(a[mid:])7    return merge(left, right)8
9
10def merge(left, right):11    out = []12    i = j = 013    while i < len(left) and j < len(right):14        if left[i] <= right[j]:15            out.append(left[i])16            i += 117        else:18            out.append(right[j])19            j += 120    out.extend(left[i:])21    out.extend(right[j:])22    return out23
24
25nums = [38, 27, 43, 3, 9, 82, 10]26print("Before:", nums)27print("After: ", merge_sort(nums))
이 코드를 Python 플레이그라운드에서 실행하기

JavaScript로 구현한 Merge Sort 코드JavaScript
1function mergeSort(arr) {2    if (arr.length <= 1) return arr;3    const mid = Math.floor(arr.length / 2);4    const left = mergeSort(arr.slice(0, mid));5    const right = mergeSort(arr.slice(mid));6    return merge(left, right);7}8
9// Merge two sorted arrays into one sorted array10function merge(left, right) {11    const out = [];12    let i = 0;13    let j = 0;14    while (i < left.length && j < right.length) {15        out.push(left[i] <= right[j] ? left[i++] : right[j++]);16    }17    return out.concat(left.slice(i), right.slice(j));18}19
20const data = [5, 2, 9, 1, 7, 3];21console.log("Before:", data);22console.log("Sorted:", mergeSort(data));
이 코드를 JavaScript 플레이그라운드에서 실행하기

Java로 구현한 Merge Sort 코드Java
1import java.util.Arrays;2
3public class Main {4    static void mergeSort(int[] arr, int left, int right) {5        if (left >= right) return;6        int mid = (left + right) / 2;7        mergeSort(arr, left, mid);8        mergeSort(arr, mid + 1, right);9        merge(arr, left, mid, right);10    }11
12    // Merge two sorted halves into a temp array, then copy back13    static void merge(int[] arr, int left, int mid, int right) {14        int[] tmp = new int[right - left + 1];15        int i = left, j = mid + 1, k = 0;16        while (i <= mid && j <= right) {17            tmp[k++] = arr[i] <= arr[j] ? arr[i++] : arr[j++];18        }19        while (i <= mid) tmp[k++] = arr[i++];20        while (j <= right) tmp[k++] = arr[j++];21        System.arraycopy(tmp, 0, arr, left, tmp.length);22    }23
24    public static void main(String[] args) {25        int[] arr = {38, 27, 43, 3, 9, 82, 10};26        System.out.println("Before: " + Arrays.toString(arr));27        mergeSort(arr, 0, arr.length - 1);28        System.out.println("After:  " + Arrays.toString(arr));29    }30}
이 코드를 Java 플레이그라운드에서 실행하기

C++로 구현한 Merge Sort 코드C++
1#include <iostream>2#include <vector>3
4void printVec(const std::vector<int>& a) {5    for (int x : a) std::cout << x << " ";6    std::cout << "\n";7}8
9void merge(std::vector<int>& a, int lo, int mid, int hi) {10    std::vector<int> tmp;11    tmp.reserve(hi - lo + 1);12    int i = lo, j = mid + 1;13    while (i <= mid && j <= hi) {14        if (a[i] <= a[j]) tmp.push_back(a[i++]);15        else tmp.push_back(a[j++]);16    }17    while (i <= mid) tmp.push_back(a[i++]);18    while (j <= hi) tmp.push_back(a[j++]);19    for (size_t k = 0; k < tmp.size(); ++k) a[lo + k] = tmp[k];20}21
22void mergeSort(std::vector<int>& a, int lo, int hi) {23    if (lo >= hi) return;24    int mid = lo + (hi - lo) / 2;25    mergeSort(a, lo, mid);      // sort the left half26    mergeSort(a, mid + 1, hi);  // sort the right half27    merge(a, lo, mid, hi);      // merge the sorted halves28}29
30int main() {31    std::vector<int> data = {38, 27, 43, 3, 9, 82, 10};32    std::cout << "Before: ";33    printVec(data);34    mergeSort(data, 0, static_cast<int>(data.size()) - 1);35    std::cout << "After:  ";36    printVec(data);37    return 0;38}
이 코드를 C++ 플레이그라운드에서 실행하기

C로 구현한 Merge Sort 코드C
1#include <stdio.h>2#include <stdlib.h>3
4void printArr(const int a[], int n) {5    for (int i = 0; i < n; i++) printf("%d ", a[i]);6    printf("\n");7}8
9void merge(int a[], int lo, int mid, int hi) {10    int* tmp = malloc((hi - lo + 1) * sizeof(int));11    int i = lo, j = mid + 1, k = 0;12    while (i <= mid && j <= hi) {13        if (a[i] <= a[j]) tmp[k++] = a[i++];14        else tmp[k++] = a[j++];15    }16    while (i <= mid) tmp[k++] = a[i++];17    while (j <= hi) tmp[k++] = a[j++];18    for (k = 0; k <= hi - lo; k++) a[lo + k] = tmp[k];19    free(tmp);20}21
22void mergeSort(int a[], int lo, int hi) {23    if (lo >= hi) return;24    int mid = lo + (hi - lo) / 2;25    mergeSort(a, lo, mid);      // sort the left half26    mergeSort(a, mid + 1, hi);  // sort the right half27    merge(a, lo, mid, hi);      // merge the sorted halves28}29
30int main(void) {31    int data[] = {38, 27, 43, 3, 9, 82, 10};32    int n = sizeof(data) / sizeof(data[0]);33    printf("Before: ");34    printArr(data, n);35    mergeSort(data, 0, n - 1);36    printf("After:  ");37    printArr(data, n);38    return 0;39}
이 코드를 C 플레이그라운드에서 실행하기

병합 정렬 자주 묻는 질문

병합 정렬의 시간 복잡도는 무엇인가요?

병합 정렬은 항상 배열을 절반으로 나누기 때문에 최선, 평균, 최악의 경우 모두 O(n log n)입니다. 병합 버퍼를 위해 O(n)의 추가 공간을 사용합니다.

병합 정렬은 안정적인가요?

예, 병합 단계가 동점을 왼쪽 절반에서 먼저 가져와 처리하는 경우 안정적입니다. 이는 같은 원소들을 원래의 상대 순서대로 유지하므로, 병합 정렬은 안정 정렬에서 흔히 선택됩니다.

quicksort 대신 병합 정렬을 쓰는 이유는 무엇인가요?

병합 정렬은 적대적인 입력에서도 O(n log n)을 보장하고 안정적인 반면, quicksort는 O(n²)으로 저하될 수 있습니다. 병합 정렬은 연결 리스트와 외부 정렬에서도 선호됩니다. 단점은 O(n)의 추가 메모리입니다.

병합 정렬과 quicksort의 차이는 무엇인가요?

둘 다 분할 정복 정렬이지만, quicksort는 피벗을 기준으로 분할하며 O(log n)의 스택 공간으로 제자리에서 정렬하고, 병합 정렬은 무조건 절반으로 나눈 뒤 O(n) 버퍼로 병합합니다. quicksort는 캐시 지역성 덕분에 실제로 대개 더 빠르지만, 병합 정렬은 보장된 O(n log n) 최악 성능을 가지며 안정적입니다.

실무에서 병합 정렬은 언제 써야 하나요?

보장된 O(n log n) 한계를 가진 안정 정렬이 필요할 때, 연결 리스트를 정렬할 때(임의 접근이 필요 없음), 또는 메모리에 담기 어려운 큰 데이터를 외부 정렬할 때 병합 정렬을 선택하세요. O(n)의 추가 공간이 필요하므로 메모리가 부족할 때는 피하세요.

병합 정렬은 제자리에서 정렬하나요?

아니요. 표준 병합 정렬은 두 절반을 병합하기 위해 O(n)의 임시 버퍼를 할당하므로 제자리 정렬이 아닙니다. 제자리 병합 변형도 있지만 복잡하고 더 느리거나 안정성을 잃기 때문에, 버퍼를 사용하는 버전이 일반적인 선택입니다.