합병 정렬

위키백과, 우리 모두의 백과사전.
이동: 둘러보기, 검색
합병 정렬
분류 정렬 알고리즘
자료구조 배열
시간복잡도 О(n log n)
공간복잡도 О(n)
최적 가끔
완전 {{{완전}}}

합병 정렬 또는 병합 정렬(merge sort)은 O(n log n) 비교 기반 정렬 알고리즘이다. 일반적인 방법으로 구현했을 때 이 정렬은 안정 정렬에 속하며, 분할 정복 알고리즘의 하나이다. 존 폰 노이만1945년에 개발했다.

알고리즘[편집]

합병 정렬은 다음과 같이 작동한다.

  1. 리스트의 길이가 0 또는 1이면 이미 정렬된 것으로 본다. 그렇지 않은 경우에는
  2. 정렬되지 않은 리스트를 절반으로 잘라 비슷한 크기의 두 부분 리스트로 나눈다.
  3. 각 부분 리스트를 재귀적으로 합병 정렬을 이용해 정렬한다.
  4. 두 부분 리스트를 다시 하나의 정렬된 리스트로 합병한다.

외부 병합 정렬(External merge sort)[편집]

external merge sort는 대상 데이터가 테이프나 디스크에 저장되어있고 데이터가 너무 커서 메모리에 담을 수 없는 경우에 실용적인 방법이다. 예를 들어, 900MB의 데이터를 100MB의 RAM을 사용하여 정렬을 해야 한다고 해보자. 1. 100MB 데이터를 주메모리에 읽어들이고, quicksort와 같이 일반적인 알고리즘을 사용하여 정렬한다. 2. 정렬된 데이터를 디스크에 쓴다. 3. 1,2 번 과정을 9번 반복한다. 그러면 100MB짜리 파일이 9개 생긴다. 4. 9개의 파일에서 각각 처음부터 10MB 씩을 메모리(입력버퍼)에 로딩한다. 10MB의 출력을 위한 버퍼도 만들어둔다. 5. 9way merge를 수행하고 결과를 출력버퍼에 쓴다. 출력버퍼가 차면 파일에 쓰고, 출력 버퍼를 비운다. 9개의 입력 버퍼가 비워지면, 다음 10MB를 읽는다.


참조 자료[편집]