노트

병합 정렬

Merge Sort

CS#algorithm · 연결된 개념 4개

쉽게 말하면

병합 정렬은 카드 더미를 한 장씩 될 때까지 반으로 나눈 뒤, 정렬된 두 더미의 맨 위 카드를 비교해 작은 것부터 내려놓으며 합치는 방식이에요. 입력이 어떤 모양이든 늘 O(n log n)이에요.

비유가 깨지는 곳 카드는 내려놓을 자리만 있으면 되지만, 코드는 합칠 때 새 배열을 만들어 추가 메모리 O(n)이 들어요. 대신 같은 값의 원래 순서가 유지되는 안정 정렬이에요.

배열을 원소 하나가 될 때까지 반으로 나눈 뒤, 정렬된 조각 둘을 하나로 합치기를 반복하는 정렬. 원소 하나짜리 배열은 이미 정렬돼 있다는 점에서 출발한다. 분할 정복의 대표 예다.

function merge(a: number[], b: number[]) {
  const out: number[] = []
  let i = 0, j = 0
  while (i < a.length && j < b.length) out.push(a[i] <= b[j] ? a[i++] : b[j++])
  return out.concat(a.slice(i), b.slice(j))
}
 
function mergeSort(arr: number[]): number[] {
  if (arr.length <= 1) return arr
  const mid = Math.floor(arr.length / 2)
  return merge(mergeSort(arr.slice(0, mid)), mergeSort(arr.slice(mid)))
}
  • 나누는 단계가 log n층이고 층마다 합치는 데 O(n)이라 항상 O(n log n)이다. 입력 모양에 따라 느려지지 않는다
  • 같은 값의 원래 순서가 유지되는 안정 정렬(Stable Sort)이다(<= 덕분)
  • 새 배열을 만들며 합치므로 추가 메모리 O(n)이 든다. 제자리 병합 정렬(In-Place Merge Sort)도 있지만 훨씬 복잡하다
  • 합치기 단계는 정렬된 두 목록을 투 포인터로 훑는 것이다
  • 연결 리스트 정렬이나 메모리에 다 안 올라가는 대용량 외부 정렬(External Sorting)에 잘 맞는다

퀵 정렬와 함께 대표적인 효율적 정렬이다. 다른 정렬과의 비교는 정렬 알고리즘.

연결된 개념

이 노트를 가리키는 문서

뜻이 가까운 노트

  • 이진 탐색

    정렬된 배열에서 가운데 값과 찾는 값을 비교해 매번 절반을 버리며 찾는 방법. 원소가 100만 개여도 20번 남짓이면 끝난다(O(log n)). 처음부터 하나씩 확인하는 선형 탐색(Linear Search)은 O(n)이다.

  • 이진 힙

    부모가 항상 자식보다 크거나(최대 힙, Max Heap) 작은(최소 힙, Min Heap) 완전 이진 트리(Complete Binary Tree). 형제끼리의 순서는 정하지 않는다. 가장 크거나 작은 값이 항상 루트에 있어 꺼내기 쉽다.

  • 빅오 표기법

    입력 크기 n이 커질 때 알고리즘의 실행 시간(시간 복잡도, Time Complexity)이나 메모리(공간 복잡도, Space Complexity)가 얼마나 빨리 늘어나는지를 대략적으로 나타내는 표기. 정확한 횟수가 아니라 증가하는 모양을 본다. 그래서 상수와 작은 항은 버린다(2n + 5는 O(n)).

  • 재귀

    함수가 자기 자신을 다시 호출해 문제를 푸는 방식. 같은 함수를 점점 작은 입력으로 부르다가 더 나눌 필요가 없는 지점(기저 조건, Base Case)에서 멈춘다.

  • 피셔-예이츠 셔플

    배열을 모든 순열(Permutation)이 같은 확률로 나오도록 섞는 알고리즘. 끝에서부터 앞으로 오며, 현재 위치의 원소를 그 앞쪽(자기 포함) 중 무작위로 고른 원소와 바꾼다.

보기 옵션