구현

이 장에서는 병합 정렬과 퀵 정렬을 Python으로 구현하고 한 줄씩 설명합니다. 이어서 같은 병합 정렬을 C++, Java, TypeScript로 옮겨 언어마다 무엇이 달라지는지 봅니다.

Python 병합 정렬

def merge_sort(items):
    if len(items) <= 1:
        return items[:]
    mid = len(items) // 2
    left = merge_sort(items[:mid])
    right = merge_sort(items[mid:])
    return merge(left, right)


def merge(left, right):
    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


print(merge_sort([38, 27, 43, 3, 9, 82, 10]))  # [3, 9, 10, 27, 38, 43, 82]

• len(items) <= 1: 원소가 0개나 1개면 이미 정렬된 상태입니다. 재귀의 바닥입니다. items[:]로 복사본을 돌려주어 입력을 바꾸지 않는다는 약속을 지킵니다.
• mid = len(items) // 2: 가운데에서 나눕니다. 길이가 홀수면 오른쪽이 하나 더 깁니다.
• merge_sort(items[:mid]), merge_sort(items[mid:]): 두 절반을 각각 재귀로 정렬합니다.
• merge의 while: 두 목록의 맨 앞(left[i], right[j])을 비교해 작은 쪽을 붙입니다.
• left[i] <= right[j]: <=가 핵심입니다. 같을 때 왼쪽을 먼저 꺼내므로 원래 순서가 유지되어 안정 정렬이 됩니다. <로 바꾸면 안정성이 깨집니다.
• extend: 한쪽이 먼저 바닥나면 남은 쪽을 그대로 붙입니다. 남은 쪽은 이미 정렬되어 있습니다.

이 구현은 읽기 쉽지만 슬라이스마다 새 리스트를 만들기 때문에 메모리 할당이 많습니다. 성능이 중요하면 버퍼 하나를 미리 만들어 인덱스로 구간을 다루는 방식(아래 C++ · Java 판)을 씁니다.

Python 퀵 정렬

import random


def quicksort(a, lo=0, hi=None):
    if hi is None:
        hi = len(a) - 1
    while lo < hi:
        lt, gt = partition3(a, lo, hi)
        if lt - lo < hi - gt:          # 작은 쪽만 재귀로
            quicksort(a, lo, lt - 1)
            lo = gt + 1
        else:
            quicksort(a, gt + 1, hi)
            hi = lt - 1


def partition3(a, lo, hi):
    pivot = a[random.randint(lo, hi)]
    lt, i, gt = lo, lo, hi
    while i <= gt:
        if a[i] < pivot:
            a[lt], a[i] = a[i], a[lt]
            lt += 1
            i += 1
        elif a[i] > pivot:
            a[i], a[gt] = a[gt], a[i]
            gt -= 1
        else:
            i += 1
    return lt, gt


data = [5, 2, 8, 2, 9, 1, 5, 5]
quicksort(data)
print(data)  # [1, 2, 2, 5, 5, 5, 8, 9]

• random.randint(lo, hi): 기준값을 무작위로 골라, 이미 정렬된 입력 같은 특정 패턴에서 O(n²)이 되는 일을 확률적으로 피합니다.
• partition3: 배열을 "기준값보다 작음 / 같음 / 큼" 세 구역으로 나누는 3분할(네덜란드 국기 문제)입니다. 끝나면 a[lo:lt]는 작고, a[lt:gt+1]은 기준값과 같고, a[gt+1:hi+1]은 큽니다. 같은 값이 많은 입력에서도 같은 값 구역을 다시 정렬하지 않으므로 느려지지 않습니다.
• elif a[i] > pivot에서 i를 늘리지 않는 이유: 뒤에서 가져온 a[gt]는 아직 검사하지 않은 값이기 때문입니다.
• while lo < hi와 "작은 쪽만 재귀": 작은 구간은 재귀로, 큰 구간은 반복문으로 처리하면 재귀 깊이가 최악에도 O(log n)으로 묶입니다. Python의 재귀 한도(기본 1000)에 걸리지 않게 하는 실용적인 장치입니다.

C++ 병합 정렬

#include <cstddef>
#include <iostream>
#include <vector>

template <typename T>
void merge_sort(std::vector<T>& a, std::vector<T>& buf, std::size_t lo, std::size_t hi) {
    if (hi - lo <= 1) return;                 // [lo, hi) 반열린 구간
    std::size_t mid = lo + (hi - lo) / 2;
    merge_sort(a, buf, lo, mid);
    merge_sort(a, buf, mid, hi);
    std::size_t i = lo, j = mid, k = lo;
    while (i < mid && j < hi) {
        if (a[j] < a[i]) buf[k++] = a[j++];   // 오른쪽이 엄격히 작을 때만 → 안정
        else buf[k++] = a[i++];
    }
    while (i < mid) buf[k++] = a[i++];
    while (j < hi) buf[k++] = a[j++];
    for (std::size_t t = lo; t < hi; ++t) a[t] = buf[t];
}

template <typename T>
void merge_sort(std::vector<T>& a) {
    std::vector<T> buf(a.size());
    merge_sort(a, buf, 0, a.size());
}

int main() {
    std::vector<int> v{38, 27, 43, 3, 9, 82, 10};
    merge_sort(v);
    for (int x : v) std::cout << x << ' ';
    std::cout << '\n';
}

C++ 판은 버퍼를 한 번만 만들고 [lo, hi) 구간을 인덱스로 다룹니다. 비교에는 operator<만 쓰므로 <가 정의된 어떤 타입에도 동작합니다. 실무에서는 std::stable_sort가 같은 역할을 합니다.

Java 병합 정렬

import java.util.Arrays;

public class MergeSort {
    public static void sort(int[] a) {
        int[] buf = new int[a.length];
        sort(a, buf, 0, a.length);
    }

    private static void sort(int[] a, int[] buf, int lo, int hi) {
        if (hi - lo <= 1) return;
        int mid = lo + (hi - lo) / 2;          // (lo + hi) / 2 의 오버플로를 피한다
        sort(a, buf, lo, mid);
        sort(a, buf, mid, hi);
        int i = lo, j = mid, k = lo;
        while (i < mid && j < hi) {
            buf[k++] = (a[j] < a[i]) ? a[j++] : a[i++];
        }
        while (i < mid) buf[k++] = a[i++];
        while (j < hi) buf[k++] = a[j++];
        System.arraycopy(buf, lo, a, lo, hi - lo);
    }

    public static void main(String[] args) {
        int[] v = {38, 27, 43, 3, 9, 82, 10};
        sort(v);
        System.out.println(Arrays.toString(v));
    }
}

System.arraycopy로 버퍼의 구간을 한 번에 되돌려 씁니다. 객체 배열이라면 Comparator<? super T>를 받아 c.compare(a[j], a[i]) < 0으로 비교하면 됩니다.

TypeScript 병합 정렬

function mergeSort<T>(items: readonly T[], compare: (a: T, b: T) => number): T[] {
  if (items.length <= 1) return items.slice();
  const mid = Math.floor(items.length / 2);
  const left = mergeSort(items.slice(0, mid), compare);
  const right = mergeSort(items.slice(mid), compare);
  const merged: T[] = [];
  let i = 0;
  let j = 0;
  while (i < left.length && j < right.length) {
    if (compare(right[j], left[i]) < 0) merged.push(right[j++]);
    else merged.push(left[i++]);
  }
  while (i < left.length) merged.push(left[i++]);
  while (j < right.length) merged.push(right[j++]);
  return merged;
}

console.log(mergeSort([38, 27, 43, 3, 9, 82, 10], (a, b) => a - b));

TypeScript 판은 비교 함수를 인자로 받아 Array.prototype.sort와 같은 약속(음수면 a가 앞)을 따릅니다. 제네릭 T 덕분에 숫자, 문자열, 객체 모두에 쓸 수 있습니다.

정리

• 병합 정렬은 같은 값일 때 왼쪽을 먼저 꺼내는 한 줄로 안정성을 지킵니다.
• 퀵 정렬은 무작위 기준값, 3분할, 작은 쪽 재귀의 세 가지로 실전에서 안전해집니다.
• 언어가 달라도 핵심은 같으며, 버퍼 재사용과 반열린 구간이 실용적인 구현의 공통점입니다.