효율적 정렬

🎯 학습 목표

이 강을 마치면 병합 정렬과 퀵 정렬이 어떻게 O(n log n)을 만들어 내는지 설명할 수 있습니다. 그리고 두 정렬의 장단점과 최악의 경우를 구분하고, 파이썬 sort()가 내부에서 무엇을 쓰는지 알게 됩니다.

8강의 O(n²) 정렬과 이번 강의 O(n log n) 정렬의 차이는 n이 100,000일 때 100억 번 대 약 170만 번입니다. 이 차이가 어디서 나오는지 이해하는 것이 목표입니다.

💡 분할 정복 — log n은 어디서 나오는가

두 정렬 모두 분할 정복(divide and conquer)이라는 전략을 씁니다. 큰 문제를 절반씩 쪼개서 풀고, 결과를 합치는 방식입니다.

병합 정렬의 동작

  [5, 2, 4, 1, 3]
        │  나눈다
   ┌────┴────┐
  [5,2]    [4,1,3]
    │         │
  ┌─┴─┐    ┌──┴──┐
 [5] [2]  [4]  [1,3]
                 │
              ┌──┴──┐
             [1]   [3]

        ← 여기서부터 합치면서 정렬한다 →

 [5] [2]  →  [2,5]
 [1] [3]  →  [1,3]
 [4] [1,3] →  [1,3,4]
 [2,5] [1,3,4] → [1,2,3,4,5]

  ▲ 왜 O(n log n)인가

   깊이(단계 수)  : 절반씩 쪼개므로 log n 단계
   각 단계의 비용 : 그 단계의 원소를 전부 훑으므로 n

   n = 8 이면
     단계 1: 크기 8 → 4+4   (8개 처리)
     단계 2: 4 → 2+2        (8개 처리)
     단계 3: 2 → 1+1        (8개 처리)
     ─────────────────────────────────
     3단계 × 8개 = 24  →  log n × n

  ▲ 합치기(merge)가 왜 O(n)인가
    두 정렬된 배열의 맨 앞만 비교하면 되기 때문이다.

     A: [2, 5]   B: [1, 3, 4]
        2 vs 1 → 1  결과 [1]
        2 vs 3 → 2  결과 [1,2]
        5 vs 3 → 3  결과 [1,2,3]
        5 vs 4 → 4  결과 [1,2,3,4]
        A만 남음 → 그대로 붙임 [1,2,3,4,5]

     각 원소를 한 번씩만 보므로 O(n)

여기서 "쪼개면 log n"이라는 2강의 감각이 다시 나옵니다. n을 절반씩 나눠 1이 될 때까지가 log n 단계이고, 각 단계에서 n개를 훑으니 곱해서 n log n입니다.

📖 퀵 정렬 — 빠르지만 최악이 있다

퀵 정렬은 기준값(피벗)을 하나 정해 작은 것은 왼쪽, 큰 것은 오른쪽으로 나눈 뒤 양쪽을 각각 정렬합니다.

퀵 정렬의 동작

  [5, 2, 8, 1, 9, 3]   피벗 = 5
        ↓ 나누기
  [2, 1, 3]   5   [8, 9]
      ↓             ↓
   피벗 2         피벗 8
  [1] 2 [3]      8 [9]
        ↓
  [1, 2, 3, 5, 8, 9]

  ▲ 평균 O(n log n)
    피벗이 중간쯤을 가르면 절반씩 줄어든다 → log n 단계

  ▲ 최악 O(n²)  ← 병합 정렬과 결정적 차이
    피벗이 항상 최솟값이거나 최댓값이면
    한쪽이 비고 다른 쪽만 1개씩 줄어든다

    [1,2,3,4,5] 에서 피벗을 항상 맨 앞으로 잡으면
      1 | [2,3,4,5]
          2 | [3,4,5]
              3 | [4,5]
                  4 | [5]
    → n단계 × n비용 = O(n²)

    ※ 이미 정렬된 입력에서 이런 일이 벌어진다.
      그래서 실무 구현은 피벗을 무작위로 고르거나
      여러 후보 중 중간값을 고른다.

항목	병합 정렬	퀵 정렬
평균	O(n log n)	O(n log n)
최악	O(n log n)	O(n²)
추가 메모리	O(n)	O(log n)
안정성	안정	불안정
실제 속도	보통	대체로 더 빠름

정리하면 병합 정렬은 안정적이고 최악이 없지만 메모리를 더 쓰고, 퀵 정렬은 메모리를 아끼고 대체로 빠르지만 최악이 존재합니다.

그렇다면 파이썬은 무엇을 쓸까요. CPython의 list.sort()는 팀소트(Timsort)를 씁니다. 병합 정렬과 삽입 정렬을 결합한 방식으로, 입력에 이미 정렬된 구간이 있으면 그것을 활용해 거의 정렬된 데이터에서 매우 빠릅니다. 그리고 안정 정렬입니다. 8강에서 파이썬 정렬이 안정하다고 한 근거가 이것입니다.

그래서 코딩 테스트에서는 정렬을 직접 구현하지 않고 sort()를 쓰는 것이 정답입니다. 직접 짠 퀵 정렬은 최악 입력에서 시간 초과가 날 수 있습니다.

💻 실전 예제 — 병합 정렬 구현과 활용

def merge(left, right):
    """정렬된 두 리스트를 합친다 → O(n)"""
    result = []
    i = j = 0
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:      # 등호가 안정성을 만든다
            result.append(left[i])
            i += 1
        else:
            result.append(right[j])
            j += 1
    result.extend(left[i:])          # 남은 쪽을 통째로 붙인다
    result.extend(right[j:])
    return result


def merge_sort(arr):
    """병합 정렬 → O(n log n)"""
    if len(arr) <= 1:                # 기저 조건 : 더 못 쪼갬
        return arr
    mid = len(arr) // 2
    left = merge_sort(arr[:mid])     # 왼쪽 절반을 정렬
    right = merge_sort(arr[mid:])    # 오른쪽 절반을 정렬
    return merge(left, right)        # 합친다


data = [5, 2, 8, 1, 9, 3]
print(merge_sort(data))              # [1, 2, 3, 5, 8, 9]
print(data)                          # 원본은 그대로

# 실무에서는 내장 정렬을 쓴다
words = ["banana", "kiwi", "apple", "fig"]
print(sorted(words, key=len))                    # 길이 오름차순
print(sorted(words, key=lambda w: (len(w), w)))  # 길이, 같으면 사전순

코드를 줄 단위로 보겠습니다.

• if len(arr) <= 1: return arr — 기저 조건입니다. 원소가 하나면 이미 정렬된 것이므로 그대로 돌려줍니다. 재귀에서 이 줄이 없으면 무한히 호출됩니다(13강).
• mid = len(arr) // 2 — 정수 나눗셈으로 중간 지점을 구합니다.
• merge_sort(arr[:mid]) — 슬라이싱이 복사라는 점을 기억하세요(3강). 이 구현은 매 단계에서 새 리스트를 만들어 공간 O(n)을 씁니다.
• while i < len(left) and j < len(right) — 두 리스트의 맨 앞끼리만 비교합니다. 이미 각각 정렬돼 있으므로 이것으로 충분합니다.
• if left[i] <= right[j] — 등호가 핵심입니다. 값이 같을 때 왼쪽(원래 앞쪽)을 먼저 넣으므로 안정성이 보장됩니다. <로 바꾸면 불안정해집니다.
• result.extend(left[i:]) — 한쪽이 끝나면 남은 쪽은 이미 정렬돼 있으므로 통째로 붙이면 됩니다.
• sorted(words, key=len) — len 함수 자체를 key로 넘깁니다. 각 원소의 길이를 기준으로 정렬합니다.
• key=lambda w: (len(w), w) — 8강에서 본 튜플 다중 기준입니다. 길이가 같으면 사전순으로 갑니다.

merge_sort는 원본을 바꾸지 않고 새 리스트를 반환합니다. 그래서 마지막에 data를 출력하면 원래 순서가 그대로입니다.

⚠️ 자주 하는 실수

첫째, 코딩 테스트에서 정렬을 직접 구현합니다. 시간도 오래 걸리고 버그도 납니다. sort()를 쓰세요. 정렬 구현은 원리를 이해하기 위한 학습이지 실전 도구가 아닙니다.

둘째, 재귀의 기저 조건을 빠뜨립니다. if len(arr) <= 1이 없으면 무한 재귀로 오류가 납니다. 분할 정복 코드를 짤 때 기저 조건을 가장 먼저 쓰는 습관을 들이세요.

셋째, 퀵 정렬을 직접 구현하고 최악을 잊습니다. 피벗을 항상 맨 앞이나 맨 뒤로 고르면 이미 정렬된 입력에서 O(n²)가 됩니다. 출제자가 그런 입력을 넣어 두는 경우가 실제로 있습니다.

넷째, 정렬만으로 풀 수 있는 문제를 복잡하게 풉니다. "가장 큰 k개", "중복 제거 후 개수", "겹치는 구간" 같은 문제는 정렬 한 번으로 크게 단순해지는 경우가 많습니다. 막히면 "정렬하면 쉬워지나?"를 먼저 떠올려 보세요.

다섯째, 정렬 비용을 계산에서 뺍니다. 전체 풀이가 O(n)이어도 앞에 정렬이 있으면 전체는 O(n log n)입니다. 복잡도를 보고할 때 정렬을 포함해야 합니다.

📝 핵심 요약 + 다음 강 예고

이번 강의 내용을 정리합니다.

#	기억할 것
1	분할 정복 — 절반씩 쪼개면 log n 단계
2	각 단계 비용 n × log n 단계 = O(n log n)
3	병합 정렬 — 안정, 최악도 O(n log n), 메모리 O(n)
4	퀵 정렬 — 메모리 적고 빠르지만 최악 O(n²)
5	파이썬은 팀소트 — 병합+삽입, 안정 정렬
6	실전에서는 직접 구현하지 말고 sort()
7	병합에서 등호가 안정성을 만든다

지금 해 볼 것은 merge 함수의 <=를 <로 바꿔 보는 것입니다. 같은 값을 가진 원소에 표시를 달아 정렬해 보면 순서가 뒤바뀌는 것을 확인할 수 있습니다. 안정성이 코드 한 글자에서 나온다는 것을 체감하게 됩니다.

다음 10강 「이분 탐색」에서는 정렬의 진짜 보상을 다룹니다. 정렬해 두면 O(log n)에 값을 찾을 수 있습니다. 그리고 "값을 찾는 것"을 넘어 답의 범위를 이분 탐색하는 응용까지 정리하겠습니다.

📚 참고 자료

• Sorting Techniques — Python 공식 문서
• listsort.txt — CPython 정렬 알고리즘 설명 문서
• list.sort() — Python 공식 문서