노트

병합 정렬

Merge Sort

CS#algorithm · 연결된 개념 5개

쉽게 말하면

병합 정렬은 카드 더미를 한 장씩 될 때까지 반으로 나눈 뒤, 정렬된 두 더미의 맨 위 카드를 비교해 작은 것부터 내려놓으며 합치는 방식이에요. 입력이 어떤 모양이든 늘 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)에 잘 맞는다

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

책: 7장. 정렬: 비교 함수와 안정성

연결된 개념

이 노트를 가리키는 문서

뜻이 가까운 노트

  • 이진 탐색

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

  • 이진 힙

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

  • 재귀

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

  • 피셔-예이츠 셔플

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

  • 동적 프로그래밍

    복잡한 문제를 더 작은 부분 문제로 나눠 풀되, 한 번 푼 부분 문제의 답을 저장해 다시 계산하지 않는 방법. 두 조건이 맞을 때 쓴다.

보기 옵션