병합 정렬, 퀵 정렬, 힙 정렬 실전 비교

병합/퀵/힙 정렬은 모두 O(N log N)이라 비슷해 보이지만 적용 관점이 다릅니다. 안정 정렬이 필요한지, 추가 메모리를 쓸 수 있는지, 최악 시간 보장이 필요한지가 중요합니다. 평균적으로 빠른가 하나만 보면 실전에서 쉽게 흔들립니다.

여기서는 세 정렬을 단순 속도 경쟁으로 보지 않습니다. 입력 특성과 제약 조건을 우선 보고, 그 조건에 맞는 정렬을 선택하는 흐름으로 설명합니다. 바로 적용할 수 있도록 비교 기준을 단순하게 정리합니다.

핵심 원리 맵

고급 정렬은 같은 O(N log N)이라도 비용이 어디에 모이는지가 달라서 적용 관점이 다릅니다. 코드를 보기 전에 메모리 제한과 안정성 요구를 우선 적어 두세요. 병합 정렬은 배열을 반으로 나눈 뒤 정렬 결과를 다시 합치는 방식입니다. 분할 정복으로 부분 배열을 재귀 정렬하고 선형 병합을 수행하는 안정 정렬입니다. [5,1,3,2]를 [5,1], [3,2]로 쪼개 정렬한 뒤 합치면 [1,2,3,5]가 됩니다.

퀵 정렬은 피벗을 기준으로 작은 값과 큰 값을 양쪽으로 분할하는 방식입니다. partition으로 피벗 위치를 확정하고 좌우 구간을 재귀 처리하는 제자리 분할 정복 정렬입니다. 피벗이 4라면 [3,1] |4| [7,9]처럼 구간이 나뉘고, 각 구간을 같은 방식으로 정렬합니다.

힙 정렬은 최대 힙 루트를 끝으로 보내는 과정을 반복하는 방식입니다. 배열을 최대 힙으로 만든 뒤 루트-마지막 교환과 heapify를 반복해 정렬을 완료합니다. 루트가 9인 상태라면 9를 배열 뒤로 보낸 뒤 남은 구간에서 최대 힙을 다시 복원합니다.

정렬 알고리즘 선택이 운영에 미치는 영향

대용량 로그를 정렬하면서 기존 순서를 보존해야 하면 안정성이 필요합니다. 반대로 메모리 제한이 강하면 보조 배열을 쓰는 병합 정렬이 부담될 수 있습니다. 입력 분포를 모르는 환경에서는 퀵 정렬 최악 케이스 리스크도 관리해야 합니다.

즉, 정렬은 속도 경쟁이 아니라 제약 조건 충족 문제입니다. 요구사항을 우선 고정하지 않으면 구현이 자주 뒤집힙니다.

정렬 단계 디버깅 시나리오

여기서는 오답 -> 디버깅 -> 교정 -> 검증 흐름으로 추적해, 어디서 불변식이 깨지는지 단계별로 확인합니다.

같은 입력을 세 알고리즘 관점으로 나눠 봅니다.

입력: [5, 1, 9, 3, 7]

병합 정렬은 절반으로 분할한 뒤 병합하며 안정성을 유지합니다.
퀵 정렬은 피벗 기준 분할을 반복해 평균적으로 빠르게 정렬합니다.
힙 정렬은 최대 힙 루트를 반복 추출해 제자리 정렬을 수행합니다.
핵심 차이는 보조 메모리 사용, 최악 보장, 안정성 여부입니다.

고급 정렬 방식 비교를 위한 입력 분포 기준

아래 기준으로 1차 선택을 할 수 있습니다.

안정 정렬 필수: 병합 정렬 우선
평균 성능과 캐시 친화성 중시: 퀵 정렬 우선
추가 메모리 최소화: 힙 정렬 고려
최악 시간 O(N log N) 보장 필요: 병합/힙 정렬 고려

언어 내장 정렬이 이미 검증돼 있다면 직접 구현은 학습/검증 용도인지 우선 확인해야 합니다.

고급 정렬: 안정성 중심 병합 정렬

문제 의도: 안정 정렬이 필요한 상황에서 병합 정렬 구현 패턴을 확인합니다.
입력 예시: nums=[5,1,9,3,7,2,8,6,4]
출력 예시: 오름차순 결과 [1,2,3,4,5,6,7,8,9]

main.cpp

#include <iostream>
#include <vector>
using namespace std;

vector<int> mergeSort(const vector<int>& arr) {
    if (arr.size() <= 1) return arr;
    int mid = (int)arr.size() / 2;
    vector<int> left(arr.begin(), arr.begin() + mid);
    vector<int> right(arr.begin() + mid, arr.end());
    left = mergeSort(left);
    right = mergeSort(right);

    vector<int> merged;
    int i = 0, j = 0;
    while (i < (int)left.size() && j < (int)right.size()) {
        if (left[i] <= right[j]) merged.push_back(left[i++]);
        else merged.push_back(right[j++]);
    }
    while (i < (int)left.size()) merged.push_back(left[i++]);
    while (j < (int)right.size()) merged.push_back(right[j++]);
    return merged;
}

int main() {
    vector<int> nums = {9, 4, 7, 3, 1, 8, 2, 6, 5};
    auto out = mergeSort(nums);
    for (int x : out) cout << x << " ";
    cout << "\n";
    return 0;
}

Main.java

import java.util.Arrays;

public class Main {
    static int[] mergeSort(int[] arr) {
        if (arr.length <= 1) return arr;
        int mid = arr.length / 2;
        int[] left = Arrays.copyOfRange(arr, 0, mid);
        int[] right = Arrays.copyOfRange(arr, mid, arr.length);
        left = mergeSort(left);
        right = mergeSort(right);

        int[] merged = new int[arr.length];
        int i = 0, j = 0, k = 0;
        while (i < left.length && j < right.length) {
            if (left[i] <= right[j]) merged[k++] = left[i++];
            else merged[k++] = right[j++];
        }
        while (i < left.length) merged[k++] = left[i++];
        while (j < right.length) merged[k++] = right[j++];
        return merged;
    }

    public static void main(String[] args) {
        int[] nums = {9, 4, 7, 3, 1, 8, 2, 6, 5};
        System.out.println(Arrays.toString(mergeSort(nums)));
    }
}

main.py

def merge_sort(arr):
    if len(arr) <= 1:
        return arr

    mid = len(arr) // 2
    left = merge_sort(arr[:mid])
    right = merge_sort(arr[mid:])

    merged = []
    i = j = 0

    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            merged.append(left[i])
            i += 1
        else:
            merged.append(right[j])
            j += 1

    merged.extend(left[i:])
    merged.extend(right[j:])
    return merged

nums = [9, 4, 7, 3, 1, 8, 2, 6, 5]
print(merge_sort(nums))
# 출력: [1, 2, 3, 4, 5, 6, 7, 8, 9]

main.rs

fn merge_sort(arr: &[i32]) -> Vec<i32> {
    if arr.len() <= 1 {
        return arr.to_vec();
    }
    let mid = arr.len() / 2;
    let left = merge_sort(&arr[..mid]);
    let right = merge_sort(&arr[mid..]);

    let mut merged = Vec::with_capacity(arr.len());
    let (mut i, mut j) = (0usize, 0usize);
    while i < left.len() && j < right.len() {
        if left[i] <= right[j] {
            merged.push(left[i]);
            i += 1;
        } else {
            merged.push(right[j]);
            j += 1;
        }
    }
    merged.extend_from_slice(&left[i..]);
    merged.extend_from_slice(&right[j..]);
    merged
}

fn main() {
    let nums = [9, 4, 7, 3, 1, 8, 2, 6, 5];
    println!("{:?}", merge_sort(&nums));
}

안정 정렬 핵심 정렬 기준 충돌 체크

병합 단계에서 <=를 사용하면 동일 키의 상대 순서를 보존할 수 있어 안정성이 유지됩니다. 보조 배열 비용은 들지만, 입력 분포와 무관하게 성능이 예측 가능하다는 장점이 큽니다.

평균 시간복잡도: O(N log N)
최악 시간복잡도: O(N log N)
공간복잡도: O(N)

고급 정렬: 중앙 피벗 퀵 정렬

문제 의도: 중앙 원소를 피벗으로 사용하는 기본 퀵 정렬 분할 과정을 익힙니다.
입력 예시: nums=[5,1,9,3,7,2,8,6,4]
출력 예시: 오름차순 결과 [1,2,3,4,5,6,7,8,9]

피벗 기준 분할에서 i/j 포인터가 어떻게 이동하고 어디서 재귀 구간이 갈리는지 먼저 고정하면 경계 버그를 줄일 수 있습니다.

main.cpp

#include <iostream>
#include <vector>
using namespace std;

void quickSortImpl(vector<int>& a, int lo, int hi) {
    if (lo >= hi) return;
    int pivot = a[(lo + hi) / 2];
    int i = lo;
    int j = hi;

    while (i <= j) {
        while (a[i] < pivot) i++;
        while (a[j] > pivot) j--;
        if (i <= j) {
            swap(a[i], a[j]);
            i++;
            j--;
        }
    }

    if (lo < j) quickSortImpl(a, lo, j);
    if (i < hi) quickSortImpl(a, i, hi);
}

vector<int> quickSort(vector<int> arr) {
    quickSortImpl(arr, 0, (int)arr.size() - 1);
    return arr;
}

int main() {
    vector<int> nums = {5, 1, 9, 3, 7, 2, 8, 6, 4};
    auto out = quickSort(nums);
    for (int x : out) cout << x << " ";
    cout << "\n";
    return 0;
}

Main.java

import java.util.Arrays;

public class Main {
    static void quickSortImpl(int[] a, int lo, int hi) {
        if (lo >= hi) return;
        int pivot = a[(lo + hi) / 2];
        int i = lo, j = hi;

        while (i <= j) {
            while (a[i] < pivot) i++;
            while (a[j] > pivot) j--;
            if (i <= j) {
                int t = a[i]; a[i] = a[j]; a[j] = t;
                i++; j--;
            }
        }

        if (lo < j) quickSortImpl(a, lo, j);
        if (i < hi) quickSortImpl(a, i, hi);
    }

    static int[] quickSort(int[] arr) {
        int[] a = arr.clone();
        quickSortImpl(a, 0, a.length - 1);
        return a;
    }

    public static void main(String[] args) {
        int[] nums = {5, 1, 9, 3, 7, 2, 8, 6, 4};
        System.out.println(Arrays.toString(quickSort(nums)));
    }
}

main.py

def quick_sort(arr):
    a = arr[:]

    def sort(lo, hi):
        if lo >= hi:
            return

        pivot = a[(lo + hi) // 2]
        i, j = lo, hi

        while i <= j:
            while a[i] < pivot:
                i += 1
            while a[j] > pivot:
                j -= 1
            if i <= j:
                a[i], a[j] = a[j], a[i]
                i += 1
                j -= 1

        if lo < j:
            sort(lo, j)
        if i < hi:
            sort(i, hi)

    sort(0, len(a) - 1)
    return a

nums = [5, 1, 9, 3, 7, 2, 8, 6, 4]
print(quick_sort(nums))
# 출력: [1, 2, 3, 4, 5, 6, 7, 8, 9]

main.rs

fn quick_sort(arr: &[i32]) -> Vec<i32> {
    fn sort(a: &mut Vec<i32>, lo: isize, hi: isize) {
        if lo >= hi {
            return;
        }

        let pivot = a[((lo + hi) / 2) as usize];
        let mut i = lo;
        let mut j = hi;

        while i <= j {
            while a[i as usize] < pivot {
                i += 1;
            }
            while a[j as usize] > pivot {
                j -= 1;
            }
            if i <= j {
                a.swap(i as usize, j as usize);
                i += 1;
                j -= 1;
            }
        }

        if lo < j {
            sort(a, lo, j);
        }
        if i < hi {
            sort(a, i, hi);
        }
    }

    let mut out = arr.to_vec();
    let hi = (out.len() as isize) - 1;
    if hi >= 0 {
        sort(&mut out, 0, hi);
    }
    out
}

fn main() {
    let nums = [5, 1, 9, 3, 7, 2, 8, 6, 4];
    println!("{:?}", quick_sort(&nums));
}

피벗 분할 동작 분할/병합 과정 추적

중앙 피벗 방식은 구현이 단순해서 학습과 디버깅에 유리합니다. 다만 입력 분포에 따라 분할이 한쪽으로 치우치면 재귀 깊이가 커질 수 있습니다. 그래서 실무에서는 피벗 전략 개선(랜덤/median-of-three)이나 반복 구현을 함께 검토합니다.

평균 시간복잡도: O(N log N)
최악 시간복잡도: O(N^2)
공간복잡도: 평균 O(log N), 최악 O(N)

고급 정렬: 제자리 힙 정렬

문제 의도: 추가 메모리를 줄인 제자리 힙 정렬 흐름을 확인합니다.
입력 예시: nums=[5,1,9,3,7,2,8,6,4]
출력 예시: 오름차순 결과 [1,2,3,4,5,6,7,8,9]

main.cpp

#include <functional>
#include <iostream>
#include <queue>
#include <vector>
using namespace std;

vector<int> heapSort(const vector<int>& arr) {
    priority_queue<int, vector<int>, greater<int>> h(arr.begin(), arr.end());
    vector<int> out;
    while (!h.empty()) {
        out.push_back(h.top());
        h.pop();
    }
    return out;
}

int main() {
    vector<int> nums = {10, 3, 15, 7, 8, 23, 2};
    auto out = heapSort(nums);
    for (int x : out) cout << x << " ";
    cout << "\n";
    return 0;
}

Main.java

import java.util.ArrayList;
import java.util.List;
import java.util.PriorityQueue;

public class Main {
    static List<Integer> heapSort(int[] arr) {
        PriorityQueue<Integer> h = new PriorityQueue<>();
        for (int x : arr) h.offer(x);
        List<Integer> out = new ArrayList<>();
        while (!h.isEmpty()) out.add(h.poll());
        return out;
    }

    public static void main(String[] args) {
        int[] nums = {10, 3, 15, 7, 8, 23, 2};
        System.out.println(heapSort(nums));
    }
}

main.py

import heapq

def heap_sort(arr):
    h = arr[:]
    heapq.heapify(h)

    out = []
    while h:
        out.append(heapq.heappop(h))

    return out

nums = [10, 3, 15, 7, 8, 23, 2]
print(heap_sort(nums))
# 출력: [2, 3, 7, 8, 10, 15, 23]

main.rs

use std::cmp::Reverse;
use std::collections::BinaryHeap;

fn heap_sort(arr: &[i32]) -> Vec<i32> {
    let mut h: BinaryHeap<Reverse<i32>> = BinaryHeap::new();
    for &value in arr {
        h.push(Reverse(value));
    }
    let mut out = Vec::new();
    while let Some(Reverse(x)) = h.pop() {
        out.push(x);
    }
    out
}

fn main() {
    let nums = [10, 3, 15, 7, 8, 23, 2];
    println!("{:?}", heap_sort(&nums));
}

힙 재배치 동작 정렬 결과 후속 검토

파이썬 예제는 구현 명확성을 위해 heapq를 사용했습니다. 중요한 원리는 힙에서 최소값을 반복 추출해 정렬을 완성한다는 점입니다.
낮은 수준 구현에서는 진짜 제자리 정렬로 만들 수 있지만, 파이썬에서는 가독성과 안정적 동작을 우선하는 편이 실전적입니다.

평균 시간복잡도: O(N log N)
최악 시간복잡도: O(N log N)
공간복잡도: 구현 방식에 따라 O(1) 또는 O(N)

병합/퀵/힙 구현 비용 균형점

세 알고리즘의 현실적인 균형점은 다음과 같습니다.

병합 정렬: 성능 예측 쉬움, 추가 메모리 부담
퀵 정렬: 평균 빠름, 피벗 전략 실패 시 성능 급락
힙 정렬: 최악 보장 강함, 캐시 효율과 상수항에서 불리

항상 가장 빠른 정렬은 존재하지 않으며, 문제 제약과 데이터 분포를 함께 봐야 합니다.

피벗/병합 반례와 복구 절차

고급 정렬 구현에서 자주 발생하는 오류입니다.

퀵 정렬 파티션 경계 실수로 무한 재귀 발생
병합 단계에서 남은 구간 append 누락
힙 정렬에서 최대/최소 힙 기준 혼동
동일 키 데이터에서 안정성 요구를 놓침

반례는 이미 정렬된 배열, 역순 배열, 중복 다량 배열을 반드시 포함해야 합니다.

고급 정렬 성능 경계 정리

비용 상쇄 지점 판단 시에는 평균 성능뿐 아니라 최악 입력 분포, 메모리 제약, 구현 복잡도를 함께 비교해야 합니다.

알고리즘	평균 시간	최악 시간	공간	안정성
병합 정렬	`O(N log N)`	`O(N log N)`	`O(N)`	안정
퀵 정렬	`O(N log N)`	`O(N^2)`	평균 `O(log N)`	비안정
힙 정렬	`O(N log N)`	`O(N log N)`	구현 의존	비안정

피벗·병합 실패사례 체크 포인트

파이썬 기본 정렬(Timsort)은 안정 정렬이며, 부분 정렬된 데이터에서 매우 강력합니다.
직접 구현 성능을 내장 정렬과 단순 비교하면 결론이 왜곡될 수 있습니다.
정렬 전처리(파싱, 타입 변환) 비용을 분리하지 않으면 벤치마크 해석이 틀어집니다.
실무 로그에는 데이터 크기, 중복 비율, 정렬 키 특성을 함께 기록하는 것이 좋습니다.

정렬 품질 체크포인트

안정성 요구 여부를 구현 전에 확정했는가
최악 시간 보장 필요성을 문제 조건과 연결했는가
피벗/병합/힙 경계 로직 반례를 테스트했는가
내장 정렬과 직접 구현의 사용 기준을 분리했는가

고급 정렬 비교 정리

정렬 알고리즘 선택은 복잡도 표를 읽는 작업이 아닙니다. 안정성, 메모리, 최악 보장, 구현 리스크를 동시에 고려할 때 문제 요구와 운영 현실을 모두 만족하는 결정을 할 수 있습니다.

병합 정렬, 퀵 정렬, 힙 정렬 실전 비교

목차