정렬 알고리즘 비교: 버블·퀵·병합 정렬 한눈에 정리

정렬은 거의 모든 알고리즘 문제의 전처리 단계로 등장하고, CS 면접에서는 "퀵 정렬과 병합 정렬의 차이"가 단골 질문입니다. 세 가지 대표 정렬을 원리부터 코드까지 정리합니다.

버블 정렬 — 가장 단순, 가장 느림

인접한 두 원소를 비교해 큰 값을 뒤로 보내는 과정을 반복합니다. 한 번 순회할 때마다 가장 큰 값이 맨 뒤에 "거품처럼" 올라옵니다. 구현은 쉽지만 **O(n²)**라 실전에서는 거의 쓰지 않습니다.

def bubble_sort(arr):
    n = len(arr)
    for i in range(n - 1):
        swapped = False
        for j in range(n - 1 - i):
            if arr[j] > arr[j + 1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]
                swapped = True
        if not swapped:   # 이미 정렬됐으면 조기 종료
            break
    return arr

병합 정렬 — 안정적인 O(n log n)

배열을 절반으로 계속 쪼갠 뒤(분할), 정렬된 두 부분을 합치면서(정복) 전체를 정렬합니다. 항상 O(n log n)을 보장하고 **안정 정렬(stable)**이라는 게 강점입니다. 단점은 합치는 과정에서 추가 메모리 O(n)이 필요하다는 점입니다.

def merge_sort(arr):
    if len(arr) <= 1:
        return arr
    mid = len(arr) // 2
    left = merge_sort(arr[:mid])
    right = merge_sort(arr[mid:])
    # 두 정렬된 배열 병합
    res, i, j = [], 0, 0
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            res.append(left[i]); i += 1
        else:
            res.append(right[j]); j += 1
    res.extend(left[i:])
    res.extend(right[j:])
    return res

퀵 정렬 — 평균적으로 가장 빠름

기준값(pivot)을 정해 "작은 값/같은 값/큰 값"으로 분할한 뒤 양쪽을 재귀적으로 정렬합니다. **평균 O(n log n)**이고 상수가 작아 실제로 매우 빠릅니다. 다만 피벗을 잘못 고르면(이미 정렬된 배열에서 끝값을 피벗으로) **최악 O(n²)**로 떨어집니다.

def quick_sort(arr):
    if len(arr) <= 1:
        return arr
    pivot = arr[len(arr) // 2]
    left  = [x for x in arr if x < pivot]
    mid   = [x for x in arr if x == pivot]
    right = [x for x in arr if x > pivot]
    return quick_sort(left) + mid + quick_sort(right)

함정: 위 퀵 정렬은 이해용입니다. 실무·실전에서는 추가 리스트를 만들지 않는 제자리(in-place) 분할 방식을 쓰고, 피벗을 무작위로 고르거나 중앙값을 써서 최악 케이스를 피합니다.

한눈에 비교

알고리즘	평균	최악	추가 메모리	안정성
버블 정렬	O(n²)	O(n²)	O(1)	안정
병합 정렬	O(n log n)	O(n log n)	O(n)	안정
퀵 정렬	O(n log n)	O(n²)	O(log n)	불안정

마무리 체크리스트

• 버블: 학습용. 거의 정렬된 데이터에 조기 종료를 넣으면 O(n)도 가능
• 병합: 안정성·최악 보장이 필요하거나 연결 리스트 정렬에 적합
• 퀵: 평균 속도 최강, 피벗 전략이 성패를 좌우
• 실전 코테에서는 직접 짜기보다 언어 내장 정렬(파이썬 sorted, 자바 Arrays.sort)을 쓰는 게 정답인 경우가 많습니다. 내장 정렬의 복잡도가 O(n log n)이라는 점만 기억하세요.