C/C++ 알고리즘

병합 정렬

두 절반을 재귀적으로 정렬한 뒤 순서대로 merge합니다.

병합 정렬이란?

두 절반을 재귀적으로 정렬한 뒤 순서대로 merge합니다.

Divide-and-conquer로 O(n log n)을 보장합니다.

중요한 점

빈 입력, 한 요소, 중복, 정렬된 입력을 테스트하세요.
정확성과 최적화를 분리하세요.
프로덕션에서는 standard library를 우선하세요.

병합 정렬 시각화

O(n)

재생 또는 한 단계를 눌러 비교와 데이터 이동 과정을 확인하세요.

C와 C++ 코드 예제

실행 →

main.c

#include <stdio.h>
#include <stdlib.h>

void merge_sort(int *values, int *temporary, int left, int right) {
    if (right - left < 2) return;
    int middle = (left + right) / 2;
    merge_sort(values, temporary, left, middle);
    merge_sort(values, temporary, middle, right);

    int first = left;
    int second = middle;
    int output = left;
    while (first < middle && second < right) {
        temporary[output++] = values[first] < values[second]
            ? values[first++] : values[second++];
    }
    while (first < middle) temporary[output++] = values[first++];
    while (second < right) temporary[output++] = values[second++];
    for (int index = left; index < right; ++index) {
        values[index] = temporary[index];
    }
}

int main(void) {
    int values[] = {8, 3, 6, 2, 7};
    int temporary[5];
    merge_sort(values, temporary, 0, 5);
    for (int index = 0; index < 5; ++index) {
        printf("%d ", values[index]);
    }
}

예상 출력

2 3 6 7 8

C++

실행 →

main.cpp

#include <algorithm>
#include <iostream>
#include <vector>

void merge_sort(std::vector<int>& values) {
    if (values.size() < 2) return;
    auto middle = values.begin() + values.size() / 2;
    std::vector<int> left(values.begin(), middle);
    std::vector<int> right(middle, values.end());
    merge_sort(left);
    merge_sort(right);
    std::merge(left.begin(), left.end(), right.begin(), right.end(),
               values.begin());
}

int main() {
    std::vector values{8, 3, 6, 2, 7};
    merge_sort(values);
    for (int value : values) {
        std::cout << value << ' ';
    }
}

예상 출력

2 3 6 7 8

C와 C++ 비교

둘 다 O(n) 보조 공간이 필요합니다. C는 buffer를 관리하고 C++는 vector와 standard algorithm을 씁니다.

Loop, pointer, length와 buffer가 명시적입니다.

C++

Iterator와 algorithm이 연산과 저장 방식을 분리합니다.

연습 문제

두 버전을 실행하고 수정하여 각 언어의 보장을 관찰하세요.

각 비교를 직접 추적하세요.
중복과 극값을 테스트하세요.
Standard library와 benchmark하세요.