정렬의 골드 스탠다드: O(N log N)

Contexto

이전 게시물에서 우리는 다음을 배웠습니다:

• 이진 탐색 – 복잡도 O(log N)
• 선형 효율 – 복잡도 O(N)

이제 정렬의 황금 표준인 복잡도 O(N log N) (선형 로그)으로 넘어갑니다.

대용량 데이터에 대해 확장해야 하는 모든 정렬 알고리즘(예: Merge Sort 또는 Quick Sort)은 다음을 결합하기 때문에 이 복잡도를 목표로 합니다:

• 문제를 나누는 힘 (log N)
• 결과를 선형적으로 처리하는 효율성 (N)

Merge Sort가 O(N log N)을 달성하는 방법

Merge Sort(병합 정렬)는 고전적인 Divide and Conquer 예시입니다. 이 알고리즘은 두 단계로 동작하며, 이는 복잡도 **O(N log N)**과 직접적으로 연결됩니다:

1. 재귀적 분할

   • 알고리즘은 리스트를 절반씩 나누어, 결국 원소가 하나만 남는 리스트(기본 사례)가 될 때까지 진행합니다.
   • 예: 1 000 000개의 아이템이 있을 경우 ≈ 20번만 분할하면 됩니다(log₂ 1 000 000 ≈ 20).
   • log N은 재귀 트리의 높이를 나타냅니다.

2. 병합

   • 재귀의 각 레벨(총 log N 레벨)에서 알고리즘은 정렬된 리스트들을 다시 하나의 더 큰 정렬된 리스트로 결합합니다.
   • 두 리스트를 합쳐서 N개의 요소가 되도록 병합하려면 최대 N번의 비교가 필요합니다.
   • 이 연산은 본질적으로 O(N)(선형)입니다.

각 log N 레벨마다 **O(N)**을 수행하므로 전체 복잡도는 **O(N log N)**이 됩니다.

Elixir에서 O(N)인 merge 함수

효율적인 Merge Sort의 핵심은 병합 함수가 엄격히 **O(N)**을 보장하도록 하는 것입니다. Elixir에서는 다음을 의미합니다:

• 느린 연결 연산자(++)를 절대 사용하지 않기
• 리스트의 머리만을 다루기

병합 코드

## --- O(N) 병합의 핵심 ---

## 하나의 리스트가 소진될 때의 기본 경우:
defp merge([], list_b), do: list_b
defp merge(list_a, []), do: list_a

## 주요 재귀 절
defp merge([h_a | t_a] = list_a, [h_b | t_b] = list_b) do
  if h_a <= h_b do
    # h_a가 더 작음: 결과 앞에 넣고 재귀 계속
    # A의 꼬리(t_a)와 전체 리스트 B(list_b)를 사용
    [h_a | merge(t_a, list_b)]
  else
    # h_b가 더 작음: 결과 앞에 넣고 재귀 계속
    # 전체 리스트 A(list_a)와 B의 꼬리(t_b)를 사용
    [h_b | merge(list_a, t_b)]
  end
end

전체 Merge Sort 구현

defmodule MergeSort do
  @doc "Elixir에서 구현한 Merge Sort (O(N log N))."
  def sort(list) do
    case list do
      [] -> []                     # 기본 경우
      [_] -> list                  # 기본 경우
      _ ->
        # 1. 분할
        {low, high} = split_list(list)

        # 2. 재귀
        sorted_low  = sort(low)
        sorted_high = sort(high)

        # 3. 병합
        merge(sorted_low, sorted_high)
    end
  end

  ## 🛠️ 보조 분할 함수 (오류 수정을 위해 추가)
  # 리스트 길이를 찾고 리스트를 나누는 O(N) 연산.
  defp split_list(list) do
    # 리스트의 중간 지점 찾기
    len = length(list)
    split_point = trunc(len / 2)

    # Enum.split은 지정된 지점에서 리스트를 나눔 (O(N) 전체 리스트를 순회)
    Enum.split(list, split_point)
  end

  # 위에서 정의한 병합 함수
  defp merge([], list_b), do: list_b
  defp merge(list_a, []), do: list_a

  defp merge([h_a | t_a] = list_a, [h_b | t_b] = list_b) do
    if h_a <= h_b do
      [h_a | merge(t_a, list_b)]
    else
      [h_b | merge(list_a, t_b)]
    end
  end
end

결론

Merge Sort는 일반적인 정렬에 대해 우리가 할 수 있는 최선의 방법입니다. 모든 경우(최악, 평균, 최선)에서 O(N log N) 성능을 보장하므로 매우 안정적이고 신뢰할 수 있습니다.

다음 게시물 – **O(N)**의 고급 활용: 두 포인터 기법을 사용해 Squares of a Sorted Array 문제를 해결하고, O(N log N) 정렬을 단일 O(N) 단계로 변환합니다. 또한 Elixir 맵의 O(1) 비밀(구조 HAMT)도 공개합니다.