맨위로가기

합병 정렬

"오늘의AI위키"는 AI 기술로 일관성 있고 체계적인 최신 지식을 제공하는 혁신 플랫폼입니다.
"오늘의AI위키"의 AI를 통해 더욱 풍부하고 폭넓은 지식 경험을 누리세요.
목차

1. 개요

합병 정렬은 정렬되지 않은 리스트를 재귀적으로 분할하고 정렬한 후 병합하는 분할 정복 알고리즘이다. 리스트를 단일 요소 리스트로 나누고 병합하여 정렬된 리스트를 생성한다. 하향식, 상향식, 외부 정렬, 자연 정렬 등 다양한 구현 방식이 있으며, 병렬 처리에 적합하다. 평균 및 최악의 경우 O(n log n)의 시간 복잡도를 가지며, 퀵 정렬보다 안정 정렬이며, 연결 리스트 정렬에 적합하다. 데이터베이스 시스템, 검색 엔진, 빅데이터 분석, 정보통신 기술 등 한국 정보화 사회에서 널리 활용된다.

더 읽어볼만한 페이지

  • 안정 정렬 - 삽입 정렬
    삽입 정렬은 미정렬 부분의 원소를 정렬된 부분의 올바른 위치에 삽입하여 정렬을 완성하는 간단하고 효율적인 알고리즘이지만, 데이터 세트가 클수록 성능이 저하되어 이를 개선하기 위한 변형 알고리즘이 존재한다.
  • 안정 정렬 - 기수 정렬
    기수 정렬은 자릿수를 기준으로 데이터를 정렬하는 비-비교 정렬 알고리즘으로, 최하위 또는 최상위 자릿수부터 시작하여 각 자릿수에 대해 안정 정렬 알고리즘을 사용하여 문자열이나 정수와 같은 데이터를 효율적으로 정렬한다.
  • 비교 정렬 - 퀵 정렬
    퀵 정렬은 토니 호어가 개발한 분할 정복 방식의 효율적인 정렬 알고리즘으로, 피벗을 기준으로 리스트를 분할하여 정렬하는 과정을 재귀적으로 반복하며 다양한 최적화 기법과 변형이 존재한다.
  • 비교 정렬 - 힙 정렬
    힙 정렬은 배열을 이진 최대 힙으로 구성하여 루트 노드와 마지막 요소를 교환하고 힙을 재구성하는 과정을 반복하며 O(n log n)의 시간 복잡도를 가지는 효율적인 정렬 알고리즘이다.
  • 정렬 알고리즘 - 퀵 정렬
    퀵 정렬은 토니 호어가 개발한 분할 정복 방식의 효율적인 정렬 알고리즘으로, 피벗을 기준으로 리스트를 분할하여 정렬하는 과정을 재귀적으로 반복하며 다양한 최적화 기법과 변형이 존재한다.
  • 정렬 알고리즘 - 힙 정렬
    힙 정렬은 배열을 이진 최대 힙으로 구성하여 루트 노드와 마지막 요소를 교환하고 힙을 재구성하는 과정을 반복하며 O(n log n)의 시간 복잡도를 가지는 효율적인 정렬 알고리즘이다.
합병 정렬
개요
종류정렬 알고리즘
자료 구조배열
시간 복잡도O(n log n)
최선의 시간 복잡도Ω(n log n) (일반적인 경우), Ω(n) (자연스러운 변형)
평균 시간 복잡도Θ(n log n)
공간 복잡도O(n) (총합, 보조 공간 O(n)), O(1) (연결 리스트)
명칭
영어Merge sort (머지 소트)
일본어マージソート (Māji sōto, 마지 소토)
기타
참고 문헌Knuth, 1998, p. 158
Katajainen & Träff, 1997

2. 알고리즘

합병 정렬은 대표적인 분할 정복 방식에 기반한 정렬 알고리즘이다. 기본적인 아이디어는 정렬되지 않은 리스트를 더 이상 나눌 수 없을 때까지 작은 부분리스트로 분할하고, 각 부분리스트를 정렬한 다음 다시 순서대로 병합하여 전체 리스트를 정렬하는 것이다.

개념적으로 다음과 같이 작동한다.

# 정렬되지 않은 리스트를 각 원소가 하나만 포함된 ''n''개의 부분리스트로 나눈다. (원소가 하나인 리스트는 이미 정렬된 상태로 간주한다.)

# 부분리스트가 단 하나만 남을 때까지, 인접한 두 개의 부분리스트를 병합하여 정렬된 새로운 부분리스트를 만드는 과정을 반복한다. 최종적으로 남는 하나의 리스트가 완전히 정렬된 결과이다.

흔히 사용되는 방식은 재귀적인 접근법으로, 리스트를 절반으로 나누는 과정을 반복하고, 나누어진 작은 리스트들이 정렬되면 이를 다시 합쳐나가는 방식으로 동작한다. 이 과정은 크게 분할(divide), 정복(conquer), 결합(combine) 단계로 나눌 수 있으며, 세부적인 작동 방식과 다양한 구현 기법은 하위 섹션에서 더 자세히 설명한다.

2. 1. 작동 방식

합병 정렬은 기본적으로 분할 정복 전략에 기반한다. 작동 원리는 다음과 같다.

# 정렬되지 않은 리스트를 각 원소가 하나만 포함된 ''n''개의 부분리스트로 나눈다. 원소가 하나인 리스트는 이미 정렬된 상태로 간주한다.

# 부분리스트가 단 하나만 남을 때까지, 인접한 두 개의 부분리스트를 병합하여 정렬된 새로운 부분리스트를 만드는 과정을 반복한다. 최종적으로 남는 하나의 리스트가 완전히 정렬된 결과이다.

가장 널리 사용되는 하향식 2-way 합병 정렬의 구체적인 작동 단계는 다음과 같다.

# 분할(Divide): 정렬할 리스트의 원소 개수가 1개 이하라면 이미 정렬된 것으로 보고 종료한다. 그렇지 않다면, 리스트를 거의 같은 크기의 두 부분 리스트로 나눈다.

# 정복(Conquer): 나누어진 두 개의 부분 리스트 각각에 대해 재귀적으로 합병 정렬을 호출하여 정렬한다.

# 결합(Combine): 정렬된 두 개의 부분 리스트를 하나의 정렬된 리스트로 병합한다. 이 과정에서 정렬 결과는 보통 임시 배열에 저장된다.

# 복사(Copy): 임시 배열에 저장된 정렬 결과를 원래 배열로 복사한다.

병합 단계(결합 단계)에서는 두 부분 리스트의 첫 번째 원소끼리 비교하여 더 작은 값을 결과 리스트에 추가하고, 해당 원소를 원래 부분 리스트에서 제거한다. 이 과정을 두 부분 리스트 중 하나가 빌 때까지 반복하고, 남은 다른 리스트의 모든 원소를 결과 리스트에 순서대로 추가한다.

데이터가 순차적으로 주어지는 경우, 온라인 알고리즘처럼 부분 데이터를 먼저 정렬하고 나중에 병합하는 방식으로 변형하여 적용할 수도 있다.

퀵 정렬과 마찬가지로 합병 정렬도 성능 개선을 위해 특정 기법을 사용하기도 한다. 리스트를 계속 분할하다가 원소의 개수가 미리 정한 임계값 이하로 작아지면, 재귀 호출을 멈추고 삽입 정렬과 같이 적은 데이터에 효율적인 다른 정렬 알고리즘을 사용하여 해당 부분 리스트를 정렬하는 방식이다.[33]

또한 합병 정렬은 외부 정렬에도 유용하게 사용된다. 예를 들어, 자기 테이프와 같은 순차 접근 저장 매체에 담긴 대용량 데이터를 정렬할 때 활용될 수 있다. 가장 단순한 방식으로는 4개의 테이프를 사용하여 2개는 읽기용, 2개는 쓰기용으로 번갈아 사용하며 병합 과정을 반복하는 "평형 2계열 병합" 기법이 있다. 이 기법은 컴퓨터의 주 기억 장치(RAM) 용량이 제한적이던 시절에 활발히 연구되었으며, 자세한 내용은 도널드 크누스의 저서 『The Art of Computer Programming』 §5.4에서 다루고 있다.

다음은 합병 정렬의 작동 예시이다. (초기 데이터: 8 4 3 7 6 5 2 1)

# 데이터 리스트를 절반으로 분할한다.

#: 8 4 3 7 | 6 5 2 1

# 각 부분을 다시 절반으로 분할한다.

#: 8 4 | 3 7 | 6 5 | 2 1

# 각 부분 리스트의 원소 수가 2개 이하가 되면, 각 리스트 내부에서 정렬한다.

#: 4 8 | 3 7 | 5 6 | 1 2

# 인접한 두 개의 정렬된 부분 리스트를 병합하여 더 큰 정렬된 리스트를 만든다.

#: 3 4 7 8 | 1 2 5 6

# 마지막으로 남은 두 개의 정렬된 리스트를 병합한다.

#: 1 2 3 4 5 6 7 8

2. 2. 세부 구현 방식

합병 정렬은 기본적인 아이디어를 바탕으로 다양한 방식으로 구현될 수 있다. 가장 흔히 사용되는 방식은 하향식(Top-down) 접근법이지만, 상향식(Bottom-up), 외부 병합 정렬, 자연 병합 정렬 등 여러 변형이 존재한다.

'''하향식 (Top-down) 구현'''

하향식 합병 정렬은 재귀 호출을 사용하여 문제를 작은 단위로 나누어 해결하는 방식이다. 작동 방식은 다음과 같다.

# 분할 (Divide): 정렬되지 않은 리스트를 절반으로 나누어 비슷한 크기의 두 부분 리스트로 만든다. 리스트의 길이가 1 이하이면 이미 정렬된 것으로 간주한다.

# 정복 (Conquer): 나누어진 각 부분 리스트에 대해 재귀적으로 합병 정렬을 호출하여 정렬한다.

# 결합 (Combine): 정렬된 두 부분 리스트를 하나의 정렬된 리스트로 병합한다. 이때 정렬 결과는 보통 임시 배열에 저장된다.

# 복사 (Copy): 임시 배열에 저장된 정렬된 결과를 원래 배열에 복사한다. (구현에 따라서는 복사 단계를 최소화하기 위해 원본 배열과 임시 배열의 역할을 번갈아 사용하기도 한다.)

하향식 구현의 핵심 로직은 다음과 같다.

  • 리스트 크기가 1 이하이면 종료한다.
  • 리스트를 절반으로 나눌 중간 지점을 계산한다.
  • 왼쪽 절반과 오른쪽 절반에 대해 재귀적으로 정렬 함수를 호출한다. (이때 입력 배열과 출력 배열 역할을 바꾼다.)
  • 정렬된 두 절반을 다시 원래 배열(또는 다음 단계의 입력 배열)로 병합한다. 병합 시에는 두 부분 리스트의 첫 원소부터 비교하여 작은 값을 결과 배열에 순서대로 넣는다.


'''상향식 (Bottom-up) 구현'''

상향식 합병 정렬은 재귀 호출 대신 반복문을 사용하여 구현한다. 처음에는 크기가 1인 정렬된 부분 리스트(run)들로 시작하여, 점진적으로 크기가 2, 4, 8, ...인 정렬된 부분 리스트로 병합해 나간다. 모든 원소가 하나의 정렬된 리스트에 포함될 때까지 이 과정을 반복한다.

# 부분 리스트의 크기(width)를 1부터 시작하여 리스트 전체 크기(''n'')보다 작을 때까지 2배씩 늘려가며 반복한다.

# 각 반복 단계에서, 현재 크기(width)의 인접한 두 부분 리스트를 병합하여 크기 2 * width의 정렬된 부분 리스트를 만든다. 이 결과는 보조 배열에 저장된다.

# 모든 부분 리스트 쌍에 대해 병합을 수행한 후, 다음 단계를 위해 보조 배열의 내용을 원래 배열로 복사하거나, 더 효율적인 구현에서는 다음 단계에서 원본 배열과 보조 배열의 역할을 바꾼다.

상향식 구현의 핵심 로직은 다음과 같다.

  • 병합할 부분 리스트의 크기(width)를 1부터 시작하여 2배씩 증가시킨다.
  • 각 크기(width)에 대해, 배열 전체를 순회하며 인접한 두 개의 부분 리스트(각각 크기 width)를 병합하여 크기 2*width의 정렬된 부분 리스트를 만든다.
  • 병합 과정은 하향식과 동일하게 두 부분 리스트의 원소를 비교하여 작은 값부터 결과 배열에 채워 넣는다.


'''외부 병합 정렬 (External Merge Sort)'''

합병 정렬은 자기 테이프와 같은 순차 접근 저장 장치를 사용하여 메모리에 담기 힘든 대용량 데이터를 정렬하는 데 효과적이었다. 사진은 IBM 729 자기 테이프 드라이브이다.


외부 병합 정렬은 정렬해야 할 데이터가 너무 커서 메모리에 한 번에 모두 올릴 수 없을 때 사용되는 방식이다. 데이터는 디스크나 자기 테이프와 같은 외부 저장 장치에 저장된다.

작동 방식은 대량의 데이터를 메모리에 적재 가능한 작은 단위(chunk)로 나누어 처리하는 것이다.

# 데이터를 메모리 크기에 맞는 작은 단위로 나눈다.

# 각 단위를 메모리로 읽어 들여 퀵 정렬 등 내부 정렬 알고리즘으로 정렬한다.

# 정렬된 각 단위를 외부 저장 장치(디스크 파일 등)에 임시로 저장한다. 이를 '런(run)'이라고 한다.

# 모든 데이터가 정렬된 런으로 만들어지면, 이 런들을 병합하여 최종적인 정렬된 결과를 만든다. 이때도 메모리 제약 때문에 한 번에 모든 런을 병합하지 못할 수 있으므로, 여러 개의 런을 조금씩 읽어와 병합하는 다중 경로 병합(multiway merge) 방식을 사용한다. 예를 들어, 9개의 런이 있다면 각 런에서 일부 데이터만 메모리의 입력 버퍼로 가져와 병합하고, 결과를 출력 버퍼에 쓴 뒤 디스크에 저장하는 식이다.

과거에는 자기 테이프를 외부 저장 장치로 많이 사용했으며, 보통 4개의 테이프 드라이브를 이용하여 2-way 병합을 반복 수행했다. 초기 단계에서 내부 정렬을 통해 가능한 긴 런을 만드는 하이브리드 알고리즘을 사용하면 전체 처리 단계를 줄여 효율을 높일 수 있다. 크누스가 제안한 '스노우 플로우(snowplow)' 기법(이진 힙 기반)은 사용 가능한 메모리 크기의 평균 두 배 길이의 초기 런을 생성할 수 있다.[18] 테이프 사용을 최적화하기 위한 다상 합병 정렬과 같은 더 정교한 기법도 존재한다.

'''자연 병합 정렬 (Natural Merge Sort)'''

자연 병합 정렬은 상향식 병합 정렬과 유사하지만, 입력 데이터에 이미 존재하는 정렬된 부분(이를 '런(run)' 또는 '시퀀스 런'이라고 함)을 활용하여 효율을 높이는 방식이다. 데이터가 무작위처럼 보여도 우연히 정렬된 짧은 런들이 존재하기 마련이다. 자연 병합 정렬은 이러한 자연적인 런들을 찾아내어 병합 대상으로 삼는다.

# 입력 데이터에서 이미 정렬되어 있는 연속된 부분(런)을 찾는다. 오름차순 런뿐만 아니라, 내림차순 런(읽으면서 순서를 뒤집으면 오름차순 런이 됨)도 활용할 수 있다.

# 찾아낸 런들을 FIFO 큐나 LIFO 스택과 같은 자료 구조에 저장한다.

# 큐나 스택에서 런들을 꺼내어 상향식 방식과 유사하게 병합한다. 모든 런이 하나의 정렬된 리스트로 합쳐질 때까지 반복한다.

입력 데이터에 긴 런이 많을수록 병합해야 할 횟수가 줄어들어 더 적은 단계(pass)만으로 정렬을 완료할 수 있다. 최상의 경우, 입력 데이터가 이미 전체적으로 정렬되어 있다면 (즉, 런이 하나뿐이라면) 데이터를 한 번만 훑어보는 것으로 정렬이 끝난다. 많은 실제 데이터에서 긴 자연 런이 발견되기 때문에, 자연 병합 정렬은 팀소트와 같은 효율적인 정렬 알고리즘의 핵심 구성 요소로 사용된다.[9]

예시:

  • 시작: `3 4 2 1 7 5 8 9 0 6`
  • 런 찾기: `(3 4) (2) (1 7) (5 8 9) (0 6)`
  • 1차 병합: `(2 3 4) (1 5 7 8 9) (0 6)`
  • 2차 병합: `(1 2 3 4 5 7 8 9) (0 6)`
  • 3차 병합: `(0 1 2 3 4 5 6 7 8 9)`


'''핑퐁 병합 정렬 (Ping-pong Merge Sort)'''

일반적인 병합 정렬이 두 개의 정렬된 블록을 병합하는 것과 달리, 핑퐁 병합 정렬은 네 개의 정렬된 블록을 한 번에 처리하여 데이터 이동 횟수를 줄이려는 시도이다.

# 네 개의 정렬된 블록을 동시에 보조 공간(임시 배열)으로 병합하여 두 개의 더 큰 정렬된 블록을 만든다.

# 이 두 개의 정렬된 블록을 다시 원래 메모리 공간으로 병합한다.

이 방식은 데이터를 임시 공간으로 복사했다가 다시 원래 공간으로 가져오는 작업을 줄여, 전체 데이터 이동 횟수를 절반으로 감소시키는 효과를 목표로 한다. 이 아이디어는 2014년 WikiSort에서 처음 구현되었고, 같은 해 인내 정렬의 최적화 기법으로 소개되며 '핑퐁 병합'이라는 이름이 붙었다.[10][11] 2020년 Quadsort 알고리즘에서도 이 방법을 구현하여 '쿼드 병합(quad merge)'이라고 불렀다.[12]

'''제자리 병합 정렬 (In-place Merge Sort)'''

배열을 사용하는 합병 정렬의 주요 단점 중 하나는 정렬 과정에서 원본 데이터 크기만큼의 추가적인 메모리 공간(''O''(''n''))이 필요하다는 점이다. 이를 개선하기 위해 추가 메모리 사용량을 줄이거나 아예 사용하지 않는 제자리(in-place) 병합 정렬 방식들이 연구되었다.

  • Kronrod (1969): 상수 크기의 추가 공간(''O''(1))만 사용하는 병합 정렬의 변형을 제안했다.[13]
  • Katajainen 등: 상수 양의 작업 메모리만 필요로 하는 알고리즘을 제시했지만, 안정 정렬(stable sort)이 아니라는 단점이 있다.[13]
  • 제자리 병합 알고리즘: 기존 병합 정렬과 결합하여 제자리에서 작동하도록 만드는 연구들이 진행되었다. 여기서 '제자리'는 엄밀히 말해 추가 공간이 전혀 없는 것이 아니라, 재귀 호출에 필요한 로그 수준의 스택 공간(''O''(log ''n'')) 정도만 사용하는 것을 의미하기도 한다.
  • Geffert 등은 상수 추가 공간으로 ''O''(''n'' log ''n'') 시간에 안정적인 제자리 병합이 가능함을 보였으나, 알고리즘이 매우 복잡하고 실제 성능(상수 인자)이 좋지 않았다.[14]
  • Bing-Chao Huang과 Michael A. Langston은 '실용적인 제자리 병합(practical in-place merge)' 알고리즘을 제안했다. 이는 고정된 양의 추가 공간만 사용하며 선형 시간(''O''(''n''))에 병합을 수행한다. 표준 병합 정렬보다 약간 느릴 수 있고 일부 경우 안정적이지 않지만, 실용적인 측면에서 더 효율적이다.[15]
  • SymMerge는 ''O''((''n'' + ''m'') log (''n'' + ''m'')) 시간이 걸리지만 안정적인 제자리 병합 알고리즘이다.[16]
  • 블록 병합 정렬 (Block Merge Sort): 최근에 개발된 안정적이고 선형 시간 복잡도를 가지는 제자리 병합 방식으로, 데이터의 일부를 스왑 공간으로 활용한다.
  • 이진 검색과 회전: 이진 검색과 배열 회전 기법을 사용하여 공간 복잡도를 ''O''(√''n'')으로 줄이는 방법도 있다. 이 방식은 C++ STL의 `stable_sort`나 Quadsort 등에서 사용된다.[17][12]
  • 연결 리스트 활용: 데이터를 직접 이동하는 대신, 각 데이터(키)에 다음 데이터의 위치를 가리키는 포인터(링크)를 추가하여 연결 리스트처럼 관리하는 방식이다. 병합 과정에서는 데이터 이동 없이 링크 값만 변경하므로 추가 공간 사용을 줄일 수 있다. 이는 병합 정렬뿐 아니라 다른 정렬 기법에도 적용 가능한 일반적인 기법이다.


'''기타 고속화 기법'''

합병 정렬의 성능을 개선하기 위해 다른 정렬 알고리즘과 결합하는 하이브리드 방식이 사용되기도 한다.

# 하향식 분할 과정에서 부분 리스트의 크기가 특정 임계값(예: 10개 또는 20개) 이하로 작아지면, 재귀 호출을 멈춘다.

# 이렇게 작게 나누어진 부분 리스트들에 대해서는 삽입 정렬과 같이 작은 데이터셋에 효율적인 다른 정렬 알고리즘을 적용하여 정렬한다.

# 마지막으로, 정렬된 작은 부분 리스트들을 다시 병합하여 전체 리스트를 완성한다.

이 방식은 재귀 호출의 오버헤드를 줄이고, 작은 데이터셋에 더 빠른 알고리즘을 활용하여 전체적인 성능을 향상시킬 수 있다.[33]

2. 3. 소스 코드 (C/C++, Ruby, Haskell, Scheme)

다음은 다양한 프로그래밍 언어로 구현된 합병 정렬의 예시 코드이다.

=== 의사 코드 ===

합병 정렬 알고리즘의 하향식(Top-down) 구현을 위한 의사 코드는 입력 목록을 하위 목록의 크기가 1이 될 때까지 재귀적으로 더 작은 하위 목록으로 분할한 다음, 호출 스택을 따라 올라가면서 하위 목록을 병합한다.

```text

'''function''' merge_sort(''list'' m) '''is'''

// ''기저 사례: 0개 또는 1개의 요소로 이루어진 목록은 이미 정렬된 상태이다.''

'''if''' m의 길이 ≤ 1 '''then'''

'''return''' m

// ''재귀 사례: 목록을 거의 같은 크기의 두 하위 목록으로 나눈다.''

'''var''' left := 빈 목록

'''var''' right := 빈 목록

'''for each''' x '''with index''' i '''in''' m '''do'''

'''if''' i < (m의 길이) / 2 '''then'''

left에 x 추가

'''else'''

right에 x 추가

// ''두 하위 목록을 재귀적으로 정렬한다.''

left := merge_sort(left)

right := merge_sort(right)

// ''정렬된 하위 목록들을 병합한다.''

'''return''' merge(left, right)

```

이 예에서 `merge` 함수는 정렬된 왼쪽 및 오른쪽 하위 목록을 하나의 정렬된 목록으로 병합한다.

```text

'''function''' merge(left, right) '''is'''

'''var''' result := 빈 목록

// ''두 목록 중 하나가 빌 때까지 반복한다.''

'''while''' left가 비어 있지 않음 '''and''' right가 비어 있지 않음 '''do'''

'''if''' first(left) ≤ first(right) '''then'''

result에 first(left) 추가

left := rest(left) // 목록의 첫 요소를 제외한 나머지

'''else'''

result에 first(right) 추가

right := rest(right)

// ''남아 있는 요소들을 결과 목록에 추가한다 (둘 중 하나만 실행됨).''

'''while''' left가 비어 있지 않음 '''do'''

result에 first(left) 추가

left := rest(left)

'''while''' right가 비어 있지 않음 '''do'''

result에 first(right) 추가

right := rest(right)

'''return''' result

```

다음은 노드에 대한 참조(포인터)를 사용하는 연결 리스트 기반의 상향식(Bottom-up) 합병 정렬 알고리즘에 대한 의사 코드이다. 크기가 2i인 정렬된 하위 리스트들을 저장하기 위해 작은 고정 크기 배열을 사용한다. `node`는 리스트 노드를 가리키는 참조 또는 포인터이다. `merge()` 함수는 두 개의 정렬된 리스트를 병합한다.

```text

'''function''' merge_sort(''node'' head) '''is'''

// ''빈 리스트 처리''

'''if''' head = nil '''then'''

'''return''' nil

'''var''' ''node'' array[32]; // 크기 2^i 인 리스트를 저장할 배열, nil로 초기화

'''var''' ''node'' result

'''var''' ''node'' next

'''var''' ''int'' i

result := head

// ''입력 리스트의 각 노드를 처리하며 배열에 병합''

'''while''' result ≠ nil '''do'''

next := result.next; // 다음 노드 저장

result.next := nil // 현재 노드를 단일 노드 리스트로 만듦

// ''기존 배열의 리스트들과 병합''

'''for''' (i = 0; (i < 32) && (array[i] ≠ nil); i += 1) '''do'''

result := merge(array[i], result) // 같은 크기의 리스트와 병합

array[i] := nil // 병합 후 해당 슬롯 비움

// ''배열 크기 초과 방지''

'''if''' i = 32 '''then'''

i -= 1

array[i] := result // 병합된 리스트를 적절한 슬롯에 저장

result := next // 다음 노드로 이동

// ''배열에 남아있는 모든 리스트를 하나의 최종 리스트로 병합''

result := nil

'''for''' (i = 0; i < 32; i += 1) '''do'''

result := merge(array[i], result)

'''return''' result

```

=== C ===

다음은 C로 작성된 하향식(Top-down) 합병 정렬의 예시이다. 배열 `A`를 정렬하며, 배열 `B`를 임시 작업 공간으로 사용한다.



#include // for malloc, free (실제 사용 시 필요)

#include // for memcpy (실제 사용 시 필요)

// 배열 A의 iBegin부터 iEnd-1까지의 요소를 배열 B로 복사

void CopyArray(int A[], int iBegin, int iEnd, int B[])

{

for(int k = iBegin; k < iEnd; k++)

B[k] = A[k];

// 또는 memcpy(&B[iBegin], &A[iBegin], (iEnd - iBegin) * sizeof(int));

}

// 배열 B의 두 정렬된 부분 [iBegin, iMiddle-1]과 [iMiddle, iEnd-1]을

// 배열 A의 [iBegin, iEnd-1] 위치에 병합

void TopDownMerge(int B[], int iBegin, int iMiddle, int iEnd, int A[])

{

int i = iBegin, j = iMiddle;

// B 배열에서 요소를 비교하여 A 배열에 순서대로 채움

for (int k = iBegin; k < iEnd; k++) {

// 왼쪽 부분(i)이 남아있고 (오른쪽 부분(j)이 비었거나 왼쪽 요소가 작거나 같으면)

if (i < iMiddle && (j >= iEnd || B[i] <= B[j])) {

A[k] = B[i];

i = i + 1;

} else { // 오른쪽 부분(j)에서 요소를 가져옴

A[k] = B[j];

j = j + 1;

}

}

}

// 배열 A의 [iBegin, iEnd-1] 부분을 정렬하여 배열 B에 저장 (재귀 호출 시 A와 B 역할 바뀜)

void TopDownSplitMerge(int B[], int iBegin, int iEnd, int A[])

{

// 정렬할 요소가 1개 이하면 이미 정렬된 상태

if(iEnd - iBegin <= 1)

return;

// 중간 지점을 계산하여 배열을 나눔

int iMiddle = iBegin + (iEnd - iBegin) / 2; // 오버플로우 방지

// 왼쪽 부분과 오른쪽 부분을 재귀적으로 정렬 (A와 B 역할 교체)

TopDownSplitMerge(A, iBegin, iMiddle, B); // 왼쪽 부분 정렬 (결과는 B에 저장됨)

TopDownSplitMerge(A, iMiddle, iEnd, B); // 오른쪽 부분 정렬 (결과는 B에 저장됨)

// 정렬된 두 부분을 B에서 A로 병합

TopDownMerge(B, iBegin, iMiddle, iEnd, A);

}

// 합병 정렬 메인 함수

void TopDownMergeSort(int A[], int B[], int n)

{

// 원본 배열 A를 작업 배열 B로 복사

CopyArray(A, 0, n, B);

// B를 원본으로 사용하여 A에 정렬된 결과를 저장

TopDownSplitMerge(B, 0, n, A);

}

/*

// 사용 예시:

int main() {

int data[] = {5, 2, 4, 7, 1, 3, 2, 6};

int n = sizeof(data) / sizeof(data[0]);

int* work_array = (int*)malloc(n * sizeof(int)); // 작업 배열 동적 할당

if (work_array == NULL) return 1; // 할당 실패 처리

TopDownMergeSort(data, work_array, n);

for (int i = 0; i < n; i++) {

printf("%d ", data[i]);

}

printf("\n");

free(work_array); // 메모리 해제

return 0;

}

  • /



다음은 C로 작성된 상향식(Bottom-up) 합병 정렬의 예시이다. 크기가 1인 부분 배열부터 시작하여 점차 크기를 늘려가며 병합한다.



#include // for printf in main example

#include // for malloc, free

#include // for memcpy (optional)

// Helper function for min, as C doesn't have a built-in min function

int min(int a, int b) {

return (a < b) ? a : b;

}

// 배열 B의 내용을 배열 A로 복사 (상향식용)

void CopyArrayBU(int B[], int A[], int n)

{

for(int i = 0; i < n; i++)

A[i] = B[i];

// 또는 memcpy(A, B, n * sizeof(int));

}

// 배열 A의 두 정렬된 부분 [iLeft, iRight-1]과 [iRight, iEnd-1]을

// 배열 B의 [iLeft, iEnd-1] 위치에 병합

void BottomUpMerge(int A[], int iLeft, int iRight, int iEnd, int B[])

{

int i = iLeft, j = iRight;

// A 배열에서 요소를 비교하여 B 배열에 순서대로 채움

for (int k = iLeft; k < iEnd; k++) {

// 왼쪽 부분(i)이 남아있고 (오른쪽 부분(j)이 비었거나 왼쪽 요소가 작거나 같으면)

if (i < iRight && (j >= iEnd || A[i] <= A[j])) {

B[k] = A[i];

i = i + 1;

} else { // 오른쪽 부분(j)에서 요소를 가져옴

B[k] = A[j];

j = j + 1;

}

}

}

// 상향식 합병 정렬 메인 함수

void BottomUpMergeSort(int A[], int B[], int n)

{

// width는 병합할 부분 배열의 크기 (1, 2, 4, 8, ...)

for (int width = 1; width < n; width = 2 * width)

{

// 길이가 width인 정렬된 부분 배열들을 두 개씩 병합하여

// 길이가 2*width인 정렬된 부분 배열을 만듦

for (int i = 0; i < n; i = i + 2 * width)

{

// 두 부분 배열의 시작과 끝 인덱스 계산

int iLeft = i;

int iRight = min(i + width, n); // 오른쪽 부분 시작 (배열 끝 초과 방지)

int iEnd = min(i + 2 * width, n); // 병합 결과의 끝 (배열 끝 초과 방지)

// A에서 B로 병합

BottomUpMerge(A, iLeft, iRight, iEnd, B);

}

// 병합된 결과(B)를 다음 단계의 입력(A)으로 복사

CopyArrayBU(B, A, n);

// 최적화: A와 B의 역할을 교대로 바꾸면 복사 단계를 줄일 수 있음

}

}

/*

// 사용 예시:

int main() {

int data[] = {5, 2, 4, 7, 1, 3, 2, 6};

int n = sizeof(data) / sizeof(data[0]);

int* work_array = (int*)malloc(n * sizeof(int));

if (work_array == NULL) return 1;

BottomUpMergeSort(data, work_array, n);

for (int i = 0; i < n; i++) {

printf("%d ", data[i]);

}

printf("\n");

free(work_array);

return 0;

}

  • /



다음은 일본어 위키백과에서 가져온 C 구현 예시이다. 하향식 접근 방식을 사용한다.



#include

#include // for malloc, free

// 두 정렬된 부분 배열 A[left...mid-1]과 A[mid...right-1]을

// 임시 배열 B를 이용하여 병합한 후 다시 A로 복사하는 함수

void merge(int A[], int B[], int left, int mid, int right) {

int i = left; // 왼쪽 부분 배열 인덱스

int j = mid; // 오른쪽 부분 배열 인덱스

int k = 0; // 임시 배열 B의 인덱스

int l;

// 두 부분 배열의 요소들을 비교하여 작은 순서대로 B에 저장

while (i < mid && j < right) {

if (A[i] <= A[j]) {

B[k++] = A[i++];

} else {

B[k++] = A[j++];

}

}

// 남은 요소들을 B 배열로 복사

while (i < mid) { // 왼쪽 부분 배열에 남은 요소가 있다면

B[k++] = A[i++];

}

while (j < right) { // 오른쪽 부분 배열에 남은 요소가 있다면

B[k++] = A[j++];

}

// 임시 배열 B의 내용을 원본 배열 A의 해당 위치로 복사

for (l = 0; l < k; l++) {

A[left + l] = B[l];

}

}

// 배열 A의 left부터 right-1까지의 요소를 합병 정렬하는 함수

void merge_sort_recursive(int A[], int B[], int left, int right) {

int mid;

// 정렬할 요소가 1개 이하면 종료 (재귀의 기저 조건)

if (right - left <= 1) { return; }

// 중간 지점 계산

mid = left + (right - left) / 2; // 오버플로우 방지

// 왼쪽 부분 배열 정렬

merge_sort_recursive(A, B, left, mid);

// 오른쪽 부분 배열 정렬

merge_sort_recursive(A, B, mid, right);

// 정렬된 두 부분 배열 병합

merge(A, B, left, mid, right);

}

// 합병 정렬을 시작하는 함수

void merge_sort(int A[], int n) {

if (n <= 1) return; // 정렬할 필요 없음

int* B = (int*)malloc(n * sizeof(int)); // 작업용 배열 동적 할당

if (B == NULL) {

perror("Failed to allocate memory for merge sort");

return;

}

merge_sort_recursive(A, B, 0, n); // 재귀 정렬 시작

free(B); // 할당된 메모리 해제

}

int main(void) {

int a[10] = {8,4,7,2,1,3,5,6,9,10};

const int n = 10;

int i;

merge_sort(a, n); // 배열 a를 정렬 (0부터 n-1까지)

for (i = 0; i < n; i++) {

printf("%d ", a[i]);

}

printf("\n");

return 0;

}



=== C++ ===

다음은 C++로 작성된 합병 정렬의 예시이다. 범위 `[low, high]`를 정렬하며, 임시 배열 `B`를 사용한다.



#include // std::vector 사용 예시 (배열 대신 사용 가능)

#include // std::cout 사용 예시

// 범위 [low, high]를 정렬하는 함수 (A: 원본 배열, B: 임시 배열)

void mergeSort(int A[], int low, int high, int B[]){

// 1. 기저 조건: 요소가 하나거나 없으면 정렬된 상태

if(low >= high) return;

// 2. 분할: 배열을 반으로 나눔

int mid = low + (high - low) / 2; // 오버플로우 방지

// 3. 정복: 각 부분을 재귀적으로 정렬

mergeSort(A, low, mid, B);

mergeSort(A, mid + 1, high, B);

// 4. 결합: 정렬된 두 부분을 병합하여 임시 배열 B에 저장

int i = low; // 왼쪽 부분 시작 인덱스

int j = mid + 1; // 오른쪽 부분 시작 인덱스

int k = low; // 임시 배열 B의 인덱스

while (i <= mid || j <= high) {

// 왼쪽 부분이 남았고 (오른쪽 부분이 비었거나 왼쪽 요소가 작거나 같으면)

if (j > high || (i <= mid && A[i] <= A[j])) {

B[k++] = A[i++];

} else { // 오른쪽 부분 요소를 가져옴

B[k++] = A[j++];

}

}

// 5. 복사: 임시 배열 B의 내용을 원본 배열 A로 복사

for(int idx = low; idx <= high; ++idx) {

A[idx] = B[idx];

}

}

/*

// 사용 예시:

int main() {

int data[] = {8, 4, 7, 2, 1, 3, 5, 6, 9, 10};

int n = sizeof(data) / sizeof(data[0]);

int* work_array = new int[n]; // 임시 배열 동적 할당

mergeSort(data, 0, n - 1, work_array); // 정렬 실행 (인덱스는 0 ~ n-1)

for (int i = 0; i < n; ++i) {

std::cout << data[i] << " ";

}

std::cout << std::endl;

delete[] work_array; // 메모리 해제

return 0;

}

  • /



=== Ruby ===

다음은 루비로 작성된 합병 정렬의 예시이다. 원본 배열을 변경하지 않기 위해 복사본을 사용한다.



# 합병 정렬 메인 함수 (원본 배열 변경 방지 위해 dup 사용)

def mergesort(lst)

_mergesort_(lst.dup)

end

# 재귀적으로 리스트를 분할하고 병합하는 함수

def _mergesort_(lst)

len = lst.size

# 기저 사례: 리스트 크기가 1 이하면 이미 정렬된 상태

return lst if len <= 1

# 분할: 리스트를 반으로 나눔

mid = len / 2

left = lst[0...mid]

right = lst[mid...len]

# 정복 및 결합: 각 부분을 재귀적으로 정렬하고 병합

_merge_(_mergesort_(left), _mergesort_(right))

end

# 두 개의 정렬된 리스트를 병합하는 함수

def _merge_(lst1, lst2)

result = []

# 두 리스트 중 하나가 빌 때까지 반복

while !lst1.empty? && !lst2.empty?

# 작은 요소를 결과 리스트에 추가하고 해당 리스트에서 제거 (shift 사용)

if lst1.first <= lst2.first

result << lst1.shift

else

result << lst2.shift

end

end

# 남아 있는 요소들을 결과 리스트에 추가 (concat 사용)

result.concat(lst1).concat(lst2)

end

# 사용 예시:

# sorted_list = mergesort([8, 4, 7, 2, 1, 3, 5, 6, 9, 10])

# puts sorted_list.inspect # => [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]



다음은 일본어 위키백과에서 가져온 루비 구현 예시이다. `pop` 메서드를 사용하여 배열을 나누며, 이 방식은 원본 배열을 변경하므로 주의가 필요하다 (외부 함수에서 `dup`을 사용하는 이유).



# 메인 함수 (원본 배열 변경 방지)

def mergesort_jp(lst)

return _mergesort_jp_(lst.dup)

end

# 재귀 함수 (lst를 직접 변경함)

def _mergesort_jp_(lst)

len = lst.size

return lst if len <= 1

# pop 메서드를 이용하여 lst를 오른쪽 절반(lst2)과 왼쪽 절반(lst)으로 나눔

# pop(n)은 배열 끝에서 n개의 요소를 제거하고 반환함

lst2 = lst.pop(len >> 1) # len / 2 와 동일 (오른쪽 절반)

# lst는 pop 후 남은 왼쪽 절반이 됨

# 각 부분을 재귀적으로 정렬하고 병합

return _merge_jp_(_mergesort_jp_(lst), _mergesort_jp_(lst2))

end

# 두 정렬된 리스트를 병합하는 함수

def _merge_jp_(lst1, lst2)

len1, len2 = lst1.size, lst2.size

result = Array.new(len1 + len2)

i, j, k = 0, 0, 0 # result 인덱스, lst1 인덱스, lst2 인덱스

# 두 리스트의 요소를 비교하며 결과 배열 채우기

while j < len1 && k < len2 do

if lst1[j] <= lst2[k] then

result[i] = lst1[j]

j += 1

else

result[i] = lst2[k]

k += 1

end

i += 1

end

# 남은 요소들을 결과 배열에 복사

while j < len1 do

result[i] = lst1[j]

i += 1 ; j += 1

end

while k < len2 do

result[i] = lst2[k]

i += 1 ; k += 1

end

return result

end

# 사용 예시:

# sorted_list_jp = mergesort_jp([8, 4, 7, 2, 1, 3, 5, 6, 9, 10])

# puts sorted_list_jp.inspect # => [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]



=== Haskell ===

다음은 함수형 프로그래밍 언어인 하스켈로 작성된 합병 정렬의 예시이다. 패턴 매칭과 재귀를 사용하여 간결하게 표현된다.


  • - 합병 정렬 함수 정의. Ord 타입 클래스에 속하는 요소의 리스트를 정렬.

mergeSort :: Ord a => [a] -> [a]

mergeSort [] = [] -- 기저 사례: 빈 리스트는 정렬된 상태

mergeSort [x] = [x] -- 기저 사례: 요소가 하나인 리스트는 정렬된 상태

mergeSort xs = merge (mergeSort left) (mergeSort right) -- 재귀 사례

where

  • - 리스트 xs를 거의 같은 크기의 두 리스트 left와 right로 분할

(left, right) = splitAt (length xs `div` 2) xs

  • - 두 개의 정렬된 리스트를 병합하는 함수

merge :: Ord a => [a] -> [a] -> [a]

merge [] ys = ys -- 기저 사례: 왼쪽 리스트가 비면 오른쪽 리스트 반환

merge xs [] = xs -- 기저 사례: 오른쪽 리스트가 비면 왼쪽 리스트 반환

merge (x:xs) (y:ys) -- 재귀 사례: 양쪽 리스트 모두 요소가 있을 때

| x <= y = x : merge xs (y:ys) -- 왼쪽 요소가 작거나 같으면, x를 결과에 추가하고 나머지를 재귀적으로 병합

| otherwise = y : merge (x:xs) ys -- 오른쪽 요소가 작으면, y를 결과에 추가하고 나머지를 재귀적으로 병합

  • - 사용 예시:
  • - ghci> mergeSort [8, 4, 7, 2, 1, 3, 5, 6, 9, 10]
  • - [1,2,3,4,5,6,7,8,9,10]



다음은 일본어 위키백과에서 가져온 하스켈 구현 예시이다. 리스트를 반으로 나누는 대신 요소를 번갈아 분배하는 `split` 함수를 사용하며, 이 `merge` 구현은 안정 정렬이 아니다 (`x < y` 사용).


  • - 합병 정렬 함수 (일본어 위키백과 버전)

mergesortJp :: Ord t => [t] -> [t]

mergesortJp lst = case lst of

[] -> lst -- 빈 리스트

[_] -> lst -- 단일 요소 리스트

_ -> mergeJp (mergesortJp a) (mergesortJp b) -- 재귀 호출 및 병합

where

(a, b) = split lst -- 리스트를 두 부분으로 분할

  • - 두 정렬된 리스트 병합 함수 (안정 정렬 아님)

mergeJp :: Ord t => [t] -> [t] -> [t]

mergeJp [] [] = []

mergeJp xxs [] = xxs

mergeJp [] yys = yys

mergeJp xxs@(x : xs) yys@(y : ys)

| x < y = x : mergeJp xs yys -- x와 y가 같을 때 y가 먼저 올 수 있음

| otherwise = y : mergeJp xxs ys

  • - 리스트를 번갈아가며 두 리스트로 분할하는 함수

split :: [t] -> ([t], [t])

split [] = ([], [])

split (x:xs) = let (ys, zs) = split xs in (x : zs, ys) -- 첫 요소는 첫 리스트, 두번째는 두번째, ...

  • - 사용 예시:
  • - ghci> mergesortJp [3, 1, 4, 1, 5, 9, 2, 6]
  • - [1,1,2,3,4,5,6,9]



=== Scheme ===

다음은 스킴으로 작성된 합병 정렬의 예시이다. SRFI-1 (리스트 라이브러리)의 `split-at`과 SRFI-11 (let-values)을 사용한다. 처리계에 따라 SRFI 로딩 방식이 다를 수 있다.



;; 필요한 SRFI 모듈 로드 (처리계에 따라 다름)

;; 예: (use-modules (srfi srfi-1))

;; 예: (use-modules (srfi srfi-11))

;; 두 개의 정렬된 리스트 left-half와 right-half를 병합하는 함수

(define (merge left-half right-half)

(let loop ((ls left-half) (rs right-half) (result '())) ; result는 역순으로 쌓임

(cond

((null? rs) (append (reverse result) ls)) ; 오른쪽이 비면, 결과 뒤집고 남은 왼쪽 붙임

((null? ls) (append (reverse result) rs)) ; 왼쪽이 비면, 결과 뒤집고 남은 오른쪽 붙임

(else

(let ((l (car ls)) (r (car rs)))

(if (<= l r) ; 작은 요소를 result 앞에 추가 (cons)

(loop (cdr ls) rs (cons l result))

(loop ls (cdr rs) (cons r result))))))))

;; 리스트 xs를 합병 정렬하는 함수

(define (merge-

3. 분석

''n''개의 원소를 정렬할 때, 합병 정렬의 시간 복잡도는 평균적인 경우와 최악의 경우 모두 O(''n'' log ''n'')이다.[5] 이는 정렬할 리스트를 절반으로 나누어 각각 재귀적으로 정렬한 뒤(2''T''(''n''/2)), 두 개의 정렬된 부분 리스트를 합병하는 데 ''n''번의 비교 및 이동 연산이 필요한 과정( + ''n'')으로부터 도출되는 점화 관계 ''T''(''n'') = 2''T''(''n''/2) + ''n''에 기반한다. 이 시간 복잡도는 마스터 정리를 통해 유도될 수 있다.

최악의 경우, 합병 정렬에서 수행되는 비교 횟수는 (''n'' ⌈lg ''n''⌉ − 2⌈lg ''n''⌉ + 1)과 같거나 약간 작으며, 이는 대략 (''n'' lg ''n'' − ''n'' + 1)과 (''n'' lg ''n'' + ''n'' + O(lg ''n'')) 사이의 값이다.[6] 합병 정렬의 최선의 경우는 이미 정렬된 리스트를 입력으로 받을 때이며, 이때 비교 횟수는 최악의 경우의 약 절반 정도이다.[7] 무작위로 정렬된 큰 크기의 입력 리스트에 대한 평균 비교 횟수는 최악의 경우보다 약 0.2645 * ''n'' 만큼 적다.

합병 정렬은 퀵 정렬과 비교했을 때 평균 시간 복잡도는 O(''n'' log ''n'')으로 동일하지만, 퀵 정렬의 최악 시간 복잡도가 O(''n''2)인 반면 합병 정렬은 최악의 경우에도 O(''n'' log ''n'')을 보장한다는 장점이 있다. 또한, 최악의 경우 합병 정렬은 퀵 정렬이 평균적인 경우보다 약 39% 적은 비교 연산을 수행한다.[7]

합병 정렬은 대표적인 안정 정렬(Stable Sort) 알고리즘이다. 즉, 같은 값을 가지는 원소들의 상대적인 순서가 정렬 후에도 유지된다. 이러한 특성 덕분에 연결 리스트와 같이 데이터에 순차적으로 접근해야 하는 자료 구조를 정렬할 때 효율적이며, Lisp와 같은 언어에서 자주 사용된다.

하지만 합병 정렬의 가장 큰 단점은 정렬 과정에서 추가적인 메모리 공간이 필요하다는 점이다. 일반적인 구현에서는 입력 데이터의 크기만큼인 O(''n'')의 추가 메모리가 필요하며, 이는 합병 결과를 임시로 저장할 배열 때문이다.[8] 제자리 정렬(in-place sort) 방식이 아니므로 메모리 사용량이 많은 편이다.

최신 컴퓨터 환경에서는 캐시 메모리의 효율적인 사용이 중요해지면서 참조 지역성(Locality of Reference)을 높이는 방향으로 합병 정렬을 개선하려는 연구가 진행되었다. 대표적인 예로 '''타일 병합 정렬'''(Tiled Merge Sort)이 있다. 이 방식은 리스트를 작은 크기(예: CPU 캐시에 맞는 크기 S)의 하위 배열로 분할한 뒤, 각 하위 배열은 삽입 정렬과 같이 제자리 정렬이 가능하고 캐시 효율이 좋은 알고리즘으로 정렬한다. 그 후, 정렬된 하위 배열들을 일반적인 합병 정렬 방식으로 병합하여 전체 리스트를 정렬한다. 이를 통해 메모리 계층 구조를 효율적으로 활용하여 성능을 개선할 수 있다. 또한, 정렬할 데이터의 크기가 매우 작을 경우(예: 특정 임계값 이하), 재귀 호출을 멈추고 삽입 정렬과 같은 더 빠른 알고리즘으로 전환하는 방식도 성능 향상에 도움이 된다.[33]

4. 병렬 병합 정렬

병합 정렬은 분할 정복 알고리즘 방식을 사용하기 때문에 병렬화에 유리하다. 여러 병렬 처리 방식이 개발되었는데, 순차적 상향식 병합과 유사한 방식도 있고, K-way 병합 알고리즘처럼 구조가 다른 방식도 있다.

순차 병합 정렬은 분할 단계와 병합 단계로 나눌 수 있다. 분할 단계에서는 하위 배열의 크기가 1 또는 0이 될 때까지 재귀적으로 배열을 나눈다. 이 재귀 호출들을 병렬로 처리하는 것이 가장 직관적인 병렬화 방법이다.[19] 다음 의사 코드는 fork와 join 키워드를 사용하여 병렬 재귀를 구현한 병합 정렬을 보여준다.

```

// 배열 A의 lo부터 hi(미포함)까지 요소를 정렬한다.

'''알고리즘''' 병합정렬(A, lo, hi) '''는'''

'''만약''' lo + 1 < hi '''라면''' // ''요소가 2개 이상일 때''

mid := ⌊(lo + hi) / 2⌋

'''fork''' 병합정렬(A, lo, mid)

병합정렬(A, mid, hi)

'''join'''

병합(A, lo, mid, hi)

```

이 알고리즘은 순차 버전에서 약간 수정된 것이지만, 병렬화 효율이 높지 않다. 이는 순차 병합 방식이 병렬 실행의 병목 지점이 되기 때문에 속도 향상이 크지 않다. 이 방식의 스팬(span, 가장 긴 실행 경로)은 \Theta(n)으로, 순차 버전에 비해 \Theta(\log n)만큼만 개선된다(알고리즘 입문 참조).

더 나은 병렬 성능은 병렬 병합 알고리즘을 사용해야 얻을 수 있다. 코멘 등은 두 개의 정렬된 하위 배열을 하나의 정렬된 배열로 병합하는 이진 병렬 병합 알고리즘을 제시했다.[19]

이 방식은 두 배열 중 더 긴 배열의 중간 요소를 선택하고, 이 요소가 다른 배열에 삽입될 위치를 찾는다. 이를 통해 각 배열에서 선택된 요소보다 작은 요소들의 개수를 알 수 있고, 최종 정렬된 배열에서 해당 요소의 위치를 계산할 수 있다. 이렇게 나누어진 더 작은 부분 배열들에 대해 재귀적으로 병렬 병합을 수행한다.

다음은 병렬 병합 알고리즘을 사용하는 수정된 병렬 병합 정렬의 의사 코드이다(코멘 등의 방식을 따름).

```

/**


  • A: 입력 배열
  • B: 출력 배열
  • lo: 하한 인덱스
  • hi: 상한 인덱스
  • off: 출력 배열 B에서의 시작 오프셋
  • /

'''알고리즘''' 병렬합병정렬(A, lo, hi, B, off) '''는'''

len := hi - lo + 1

'''만약''' len == 1 '''이면'''

B[off] := A[lo]

'''그렇지 않으면'''

T[1..len]을 새 배열로 선언

mid := ⌊(lo + hi) / 2⌋

mid' := mid - lo + 1

'''fork''' 병렬합병정렬(A, lo, mid, T, 1)

병렬합병정렬(A, mid + 1, hi, T, mid' + 1)

'''join'''

병렬병합(T, 1, mid', mid' + 1, len, B, off)

```

최악의 경우 스팬에 대한 점화 관계는 병렬합병정렬의 재귀 호출이 병렬로 실행되므로 한 번만 고려되어 다음과 같다.

T_{\infty}^{\text{sort}}(n) = T_{\infty}^{\text{sort}}\left(\frac {n} {2}\right) + T_{\infty}^{\text{merge}}(n)

= T_{\infty}^{\text{sort}}\left(\frac {n} {2}\right) + \Theta \left( \log(n)^2\right).

(병렬 병합 절차의 복잡도에 대한 자세한 내용은 합병 정렬 참조)

이 점화식의 해는 다음과 같다.

T_{\infty}^{\text{sort}} = \Theta \left ( \log(n)^3 \right).

이 병렬 병합 알고리즘은 \Theta \left(\frac{n}{(\log n)^2}\right)의 병렬성(parallelism)을 가지며, 이는 이전의 병렬 재귀 방식보다 훨씬 높다. 실제 구현에서는 작은 배열에 대해 삽입 정렬과 같은 빠르고 안정적인 순차 정렬을 사용하고, 병합 단계의 기본 사례(base case)로 빠른 순차 병합을 결합하면 좋은 성능을 보인다.[20]

병합 정렬을 이진(2-way) 병합 방식으로만 제한할 필요는 없다. 일반적으로 2개 이상의 프로세서를 사용할 수 있으므로, k개의 정렬된 배열을 병합하는 K-방향 병합(k-way merge) 방식을 사용하는 것이 더 효율적일 수 있다. 이 방식은 PRAM(Parallel Random Access Machine) 모델에서 정렬 알고리즘을 설명하는 데 적합하다.[21][22]

4개의 프로세서 t_0에서 t_3까지의 병렬 다방향 병합 정렬 과정


정렬되지 않은 n개의 요소를 p개의 프로세서를 사용하여 정렬하는 과정은 다음과 같다.

1. 요소를 p개의 프로세서에 균등하게 분배한다. (n이 p의 배수라고 가정하면 각 프로세서는 n/p개의 요소를 가진다.)

2. 각 프로세서는 할당된 요소를 순차 정렬 알고리즘을 사용하여 로컬에서 정렬한다. 이로써 p개의 정렬된 배열 S_1, ..., S_p가 생성된다.

3. 전체 데이터에서 순위(rank)가 k = j \frac{n}{p} (단, j=1, ..., p)인 분할자(splitter) 요소 v_j를 결정한다. 즉, p개의 분할자를 찾는다.

4. 각 배열 S_i에서 이 분할자들의 위치를 이진 탐색 알고리즘으로 찾는다. 이를 통해 각 S_i는 p개의 하위 배열 S_{i,1}, ..., S_{i,p}로 분할된다. (S_{i,j} := \{x \in S_i | rank(v_{j-1}) < rank(x) \le rank(v_j)\})

5. j번째 분할 구간에 속하는 모든 하위 배열들(S_{1,j}, ..., S_{p,j})을 프로세서 j에 할당한다. 분할자가 전역 순위를 기준으로 선택되었기 때문에, 각 프로세서는 여전히 약 n/p개의 요소를 가지게 되어 부하 분산이 이루어진다. 또한, 프로세서 i에 할당된 모든 요소는 프로세서 i+1에 할당된 모든 요소보다 작거나 같다.

6. 각 프로세서는 할당받은 p개의 하위 배열들을 p-방향 병합을 사용하여 로컬에서 병합하여 최종 정렬된 배열 조각을 만든다.

7. 모든 프로세서의 결과를 순서대로 합치면 전체 데이터가 정렬된다. (별도의 최종 병합 단계는 필요 없다.)

분할자를 찾는 다중 배열 선택(multi-sequence selection) 알고리즘은 다음과 같다. p개의 정렬된 배열 S_1, ..., S_p가 주어졌을 때, 이 배열들의 합집합에서 전역 순위가 k인 요소 x를 찾는 것이 목표이다. 이 알고리즘은 각 배열 S_i에서 x보다 작은 요소들의 개수(l_i)를 반환한다.[23]

```

'''알고리즘''' msSelect(S : 정렬된 배열의 배열 [S_1,..,S_p], k : 정수) '''는'''

'''for''' i = 1 '''to''' p '''do'''

(l_i, r_i) = (0, |S_i|-1) // 각 배열의 검색 범위 초기화

'''while''' 어떤 i에 대해 l_i < r_i 인 동안 '''do'''

// 현재 검색 범위(S_j[l_j]..S_j[r_j]) 내에서 피벗(pivot) 요소를 선택한다. (예: 무작위 선택)

v := pickPivot(S, l, r)

sum_m := 0

'''for''' i = 1 '''to''' p '''do''' // 각 배열에서 피벗 v의 위치(v보다 작거나 같은 요소 수)를 이진 탐색으로 찾는다.

m_i = binarySearch(v, S_i[l_i, r_i])

sum_m := sum_m + m_i // 모든 배열에서 v보다 작거나 같은 요소들의 총 개수 (v의 전역 순위)

'''if''' sum_m >= k '''then''' // v의 전역 순위가 목표 순위 k보다 크거나 같으면, 찾는 요소는 v 이하에 있다.

r := m // 각 배열의 오른쪽 경계를 m으로 갱신 (벡터 할당)

'''else''' // v의 전역 순위가 k보다 작으면, 찾는 요소는 v보다 크다.

l := m // 각 배열의 왼쪽 경계를 m으로 갱신 (벡터 할당)

'''return''' l // 각 배열에서 최종적으로 결정된 왼쪽 경계 인덱스 l_i들을 반환

```

PRAM 모델에서 복잡도를 분석하면, ''binarySearch'' 메서드를 p개의 프로세서가 병렬로 각 시퀀스에 대해 수행하는 시간은 \mathcal{O}\left(\log\left(n/p\right)\right)이다. (원본 소스에서는 \mathcal{O}\left(p\log\left(n/p\right)\right)로 기술됨). 예상 재귀 깊이는 퀵셀렉트(Quickselect)와 유사하게 \mathcal{O}(\log(n))이다. 따라서 p개의 분할자를 병렬로 찾는 총 예상 시간은 \mathcal{O}\left(p\log(n/p)\log(n)\right)이다.

병렬 다방향 병합 정렬에 적용하면, 이 알고리즘은 i = 1,.., p에 대해 순위 i \frac n p인 모든 분할 원소를 동시에 찾기 위해 병렬로 호출되어야 한다. 이러한 분할 원소는 각 시퀀스를 p 부분으로 분할하는 데 사용될 수 있으며, 총 실행 시간은 \mathcal{O}\left(p\, \log(n/p)\log(n)\right)이다.

다음은 병렬 다방향 병합 정렬 알고리즘 전체의 의사 코드이다. (모든 프로세서가 분할 요소와 시퀀스 파티션을 적절하게 결정할 수 있도록 다중 시퀀스 선택 전후에 배리어 동기화가 있다고 가정한다.)

```

/**

  • d: 정렬되지 않은 요소 배열
  • n: 요소 수
  • p: 프로세서 수
  • return: 정렬된 배열
  • /

'''알고리즘''' 병렬다방향병합정렬(d : 배열, n : 정수, p : 정수) '''는'''

o := '''새로운''' 배열[0, n-1] // 출력 배열

'''각각 병렬로''' i = 1 '''에서''' p '''까지''' // 각 프로세서가 병렬로 실행

S_i := d[(i-1) * n/p .. i * n/p - 1] // 각자에게 할당된 길이 n/p의 배열 조각

정렬(S_i) // 로컬 정렬 수행

'''동기화''' // 모든 프로세서가 로컬 정렬을 마칠 때까지 대기

'''각각 병렬로''' i = 1 '''에서''' p '''까지'''

v_i := ms선택([S_1,...,S_p], i * n/p) // 전역 순위 i*n/p인 분할자 요소를 찾음 (모든 프로세서가 협력하거나, 마스터 프로세서가 수행)

'''동기화''' // 모든 분할자가 결정될 때까지 대기

'''각각 병렬로''' i = 1 '''에서''' p '''까지'''

(S_i,1, ..., S_i,p) := sequence_partitioning(S_i, v_1, ..., v_p) // 자신의 로컬 배열 S_i를 분할자 기준으로 p개의 하위 배열로 분할

// 프로세서 i는 다른 모든 프로세서 j로부터 j번째 하위 배열 S_j,i 를 받음 (데이터 교환 단계)

// 받은 하위 배열들(S_1,i, ..., S_p,i)을 병합하여 출력 배열의 해당 위치에 저장

o[(i-1) * n/p .. i * n/p - 1] := k방향병합(S_1,i, ..., S_p,i) // 로컬 p-way 병합 수행

'''반환''' o

```

전체 실행 시간을 분석하면 다음과 같다.

1. 로컬 정렬: 각 프로세서가 n/p개의 요소를 정렬하므로 \mathcal{O}\left( \frac n p \log \left( \frac n p \right) \right)

2. 분할자 선택: \mathcal{O}\left(p \log(n/p) \log (n) \right)

3. 로컬 p-방향 병합: 각 프로세서가 약 n/p개의 요소를 p개의 배열로부터 병합하므로 \mathcal{O}\left(\frac n p \log (p) \right) (표준적인 k-way merge 사용 시)

따라서 전체 실행 시간은 이들의 합인 \mathcal{O}\left( \frac n p \log\left(\frac n p\right) + p \log \left( \frac n p\right) \log (n) + \frac n p \log (p) \right)이다.

다방향 병합 정렬은 프로세서 수가 많을 때 확장성이 뛰어나 컴퓨터 클러스터 등에서 대용량 데이터를 정렬하는 데 적합하다. 이런 환경에서는 메모리가 비교적 풍부하여 병합 정렬의 공간 복잡도 단점이 크게 문제되지 않는다. 그러나 실제 시스템에서는 PRAM 모델에서 고려하지 않는 요소들, 예를 들어 데이터가 프로세서 캐시에 맞지 않을 때 발생하는 메모리 계층 구조 문제나 프로세서 간 데이터 교환에 따른 통신 오버헤드가 성능에 큰 영향을 미칠 수 있다.

피터 샌더스(Peter Sanders) 등은 이러한 통신 문제를 완화하기 위해 다단계(multi-level) 다방향 병합 정렬을 위한 벌크 동기식 병렬(Bulk Synchronous Parallel, BSP) 알고리즘을 제안했다.[22] 이 방식에서는 p개의 프로세서를 크기 p'인 r개의 그룹으로 나눈다. 로컬 정렬 후, 데이터를 r개의 부분으로 나누어 각 그룹에 할당하고, 그룹 내에서 다시 병렬 병합 정렬을 재귀적으로 수행한다. 이는 통신량을 줄이고, 특히 작은 메시지가 많이 발생하는 문제를 해결하는 데 도움이 된다. 프로세서 그룹은 실제 네트워크 구조(랙, 클러스터 등)에 맞춰 구성할 수 있다.

병합 정렬은 최적의 속도 향상을 달성한 초기 정렬 알고리즘 중 하나이다. 리처드 콜(Richard Cole)은 영리한 샘플링 기법을 사용하여 병합 단계를 ''O''(1) 시간에 수행하는 방법을 제시했다.[24] 다른 정교한 병렬 정렬 알고리즘들도 비슷한 또는 더 나은 시간 복잡도를 달성했다. 예를 들어, 데이비드 파워스(David Powers)는 1991년에 CRCW PRAM 모델에서 ''n''개의 프로세서를 사용하여 ''O''(log ''n'') 시간에 동작하는 병렬화된 퀵 정렬과 기수 정렬을 발표했다.[25] 파워스는 또한 배치어(Batcher)의 비트닉 병합 정렬의 파이프라인 버전이 버터플라이 정렬 네트워크에서 ''O''((log ''n'')2) 시간이 걸리지만, 실제로는 PRAM에서의 ''O''(log ''n'') 정렬보다 빠를 수 있음을 보였으며, 다양한 정렬 알고리즘의 숨겨진 오버헤드에 대해 자세히 설명했다.[26]

5. 다른 정렬 알고리즘과의 비교

힙 정렬은 합병 정렬과 동일한 시간 복잡도 (O(n log n))를 가지지만, 추가 메모리 공간을 거의 사용하지 않으며(Θ(1) 공간 복잡도)는 장점이 있다. 반면, 합병 정렬은 일반적으로 정렬 과정에서 원본 데이터 크기만큼의 추가 메모리 공간(Θ(n) 공간 복잡도)을 필요로 한다.[8][27]

퀵 정렬은 평균적으로 합병 정렬보다 빠른 성능을 보이는 경우가 많다.[27] 특히 배열과 같이 임의 접근이 빠른 데이터 구조를 정렬할 때, 퀵 정렬은 캐시 효율성 측면에서 유리할 수 있다(O(log n) 공간 복잡도).[27] 하지만 퀵 정렬은 최악의 경우 성능이 O(n2)까지 저하될 수 있으며, 안정 정렬이 아니라는 단점이 있다. 즉, 같은 값을 가진 원소들의 상대적인 순서가 정렬 과정에서 바뀔 수 있다.

반면 합병 정렬은 항상 O(n log n)의 시간 복잡도를 보장하며, 안정 정렬이라는 특징을 가진다. 또한, 연결 리스트와 같이 데이터에 순차적으로 접근해야 하는 경우 퀵 정렬보다 효율적일 수 있다.[7] 연결 리스트의 경우, 합병 정렬은 Θ(1)의 추가 공간만으로도 구현 가능하다. 이러한 특성 때문에 Lisp와 같은 언어에서 선호되기도 한다.

팀소트(Timsort)는 합병 정렬과 삽입 정렬을 결합한 하이브리드 알고리즘이다. 팀소트는 실제 데이터에서 흔히 발견되는 이미 정렬된 부분(run)을 효율적으로 활용하여 성능을 높인다. 이러한 장점 덕분에 파이썬(버전 2.3부터, 버전 3.11부터는 Powersort 병합 정책 사용)[32], 자바(객체 정렬 시, 작은 배열은 삽입 정렬 사용)[29], 안드로이드[31] 등 여러 프로그래밍 언어 및 플랫폼에서 표준 정렬 알고리즘으로 채택되어 널리 사용되고 있다. Perl 역시 버전 5.8부터 기본 정렬 알고리즘으로 합병 정렬을 사용한다.[28] 리눅스 커널에서도 연결 리스트 정렬에 합병 정렬을 사용한다.[30]

6. 한국 정보화 사회에서의 활용

합병 정렬, 특히 외부 병합 정렬(external merge sort)은 처리해야 할 데이터의 크기가 매우 커서 컴퓨터의 주 메모리에 한 번에 모두 불러올 수 없을 때 유용한 정렬 방식이다. 예를 들어, 수백 메가바이트(MB) 혹은 기가바이트(GB) 이상의 데이터를 제한된 메모리 환경에서 정렬해야 하는 경우를 생각해 볼 수 있다. 외부 병합 정렬은 전체 데이터를 메모리에 들어갈 수 있는 작은 조각들로 나누어 각각 정렬한 뒤, 정렬된 조각들을 디스크와 같은 보조 기억 장치를 활용하며 병합하는 방식으로 동작한다. 이 과정은 데이터를 여러 단계에 걸쳐 나누고 병합하며 최종적으로 전체 데이터의 정렬을 완료한다.

합병 정렬은 병렬 처리에 매우 효율적이라는 장점을 가진다. 데이터를 여러 부분으로 나누어 다수의 프로세서가 동시에 정렬 작업을 수행할 수 있기 때문에, 컴퓨터 클러스터와 같이 여러 컴퓨팅 자원을 활용하는 환경에서 대규모 데이터를 빠르게 처리하는 데 적합하다. 이러한 시스템에서는 메모리 용량이 상대적으로 덜 제한적일 수 있어, 합병 정렬이 다른 알고리즘에 비해 메모리를 더 많이 사용한다는 단점이 크게 문제되지 않는 경우가 많다.

이러한 특징 덕분에 합병 정렬, 특히 외부 병합 정렬과 병렬 합병 정렬 방식은 현대 정보화 사회의 다양한 분야에서 중요하게 활용된다. 대규모 데이터베이스 시스템에서 데이터를 효율적으로 정렬하거나, 검색 엔진이 사용자에게 검색 결과를 관련도 순으로 보여주기 위해 내부적으로 데이터를 정렬할 때, 그리고 빅데이터 분석 플랫폼에서 방대한 양의 데이터를 처리하고 분석하는 과정 등에서 합병 정렬 기반의 알고리즘이 효과적으로 사용될 수 있다. 여러 컴퓨터 자원을 묶어 사용하는 분산 환경에서는 데이터 처리 속도와 확장성이 매우 중요하므로 합병 정렬의 병렬 처리 능력이 큰 장점으로 작용한다.

다만, 실제 컴퓨터 클러스터와 같은 병렬 처리 환경에서는 단순히 알고리즘의 이론적인 성능 외에도 데이터가 프로세서의 캐시 메모리에 얼마나 잘 맞는지, 혹은 여러 프로세서 간에 데이터를 주고받을 때 발생하는 통신 지연 시간 등 메모리 계층 구조와 관련된 다양한 기술적 요소들을 함께 고려해야 한다.[22]

7. 참고 문헌


  • Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2009). 《Introduction to Algorithms》 3판.
  • Katajainen, Jyrki; Pasanen, Tomi; Teuhola, Jukka (1996). “Practical in-place mergesort”. 《Nordic Journal of Computing》 '''3''' (1): 27–40. ISSN 1236-6064. [https://web.archive.org/web/20110807033704/http://www.diku.dk/hjemmesider/ansatte/jyrki/Paper/mergesort_NJC.ps 원본] (보존됨 2011-08-07). 확인일자: 2009-04-04. CiteSeerX: [https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.22.8523 10.1.1.22.8523]. 또한 [http://citeseer.ist.psu.edu/katajainen96practical.html 실용적인 제자리 병합 정렬].
  • Knuth, Donald (1998). 〈Section 5.2.4: Sorting by Merging〉. 《The Art of Computer Programming》. Volume 3: Sorting and Searching 2판. Addison-Wesley. 158–168쪽. ISBN 0-201-89685-0.
  • Kronrod, M. A. (1969). “Optimal ordering algorithm without operational field”. 《Soviet Mathematics - Doklady》 '''10''': 744.
  • LaMarca, A.; Ladner, R. E. (1997). “The influence of caches on the performance of sorting”. 《Proc. 8th Ann. ACM-SIAM Symp. On Discrete Algorithms (SODA97)》: 370–379. CiteSeerX: [https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.31.1153 10.1.1.31.1153].
  • Skiena, Steven S. (2008). 〈4.5: Mergesort: Sorting by Divide-and-Conquer〉. 《The Algorithm Design Manual》 2판. Springer. 120–125쪽. ISBN 978-1-84800-069-8.
  • Sun Microsystems. [http://java.sun.com/javase/6/docs/api/java/util/Arrays.html Arrays API (Java SE 6)]. 확인일자: 2007-11-19.
  • Oracle Corp. [https://docs.oracle.com/javase/10/docs/api/java/util/Arrays.html Arrays (Java SE 10 & JDK 10)]. 확인일자: 2018-07-23.

참조

[1] 논문
[2] 서적 Data structures and algorithms in Python Wiley 2013
[3] 논문
[4] 간행물 Algorithms and Complexity 1997-03
[5] 논문
[6] 문서
[7] 서적 Data structure using C++ https://www.worldcat[...] Firewall Media
[8] 논문
[9] 보고서 DCS Technical Report 8313 Department of Computer Science, University of New South Wales 1983
[10] 웹사이트 WikiSort. Fast and stable sort algorithm that uses O(1) memory. Public domain. https://github.com/B[...] 2014-04-14
[11] 간행물 Patience is a Virtue: Revisiting Merge and Sort on Modern Processors http://research.micr[...]
[12] 웹사이트 Quadsort is a branchless stable adaptive merge sort. https://github.com/s[...] 2022-06-08
[13] 논문
[14] 학술지 Asymptotically efficient in-place merging
[15] 학술지 Practical In-Place Merging 1988-03
[16] 간행물 Algorithms – ESA 2004
[17] 학술지 A New Method for Efficient in-Place Merging https://koreascience[...] 2003-09-01
[18] citation The magic of Algorithms! 2009–2019
[19] 논문
[20] 뉴스 Parallel Merge Sort https://duvanenko.te[...] Dr. Dobb's Journal & blog
[21] 웹사이트 Lecture ''Parallel algorithms'' http://algo2.iti.kit[...] 2020-05-02
[22] 서적 Proceedings of the 27th ACM symposium on Parallelism in Algorithms and Architectures
[23] 웹사이트 Lecture ''Parallel algorithms'' http://algo2.iti.kit[...] 2020-05-02
[24] 학술지 Parallel merge sort 1988-08
[25] 서적 Proceedings of International Conference on Parallel Computing Technologies, Novosibirsk 1991
[26] 간행물 Parallel Unification: Practical Complexity http://david.wardpow[...] 1995-01
[27] 학술지 Comparison of quicksort and mergesort https://www.scienced[...] 2024-01-20
[28] 웹사이트 Sort – Perl 5 version 8.8 documentation https://perldoc.perl[...] 2020-08-23
[29] 웹사이트 src/java.base/share/classes/java/util/Arrays.java @ 53904:9c3fe09f69bc https://hg.openjdk.j[...] 2019-02-22
[30] 문서 linux kernel /lib/list_sort.c https://github.com/t[...]
[31] 웹사이트 Computer scientists improve Python sorting function https://techxplore.c[...] 2024-05-08
[32] 웹사이트 Python Now Uses Powersort https://www.i-progra[...] 2024-05-08
[33] 서적 C言語による最新アルゴリズム事典 技術評論社
[34] 서적 Sorting and Searching Addison-Wesley
[35] 논문
[36] 콘퍼런스 A meticulous analysis of mergesort programs http://hjemmesider.d[...] 1997-03


본 사이트는 AI가 위키백과와 뉴스 기사,정부 간행물,학술 논문등을 바탕으로 정보를 가공하여 제공하는 백과사전형 서비스입니다.
모든 문서는 AI에 의해 자동 생성되며, CC BY-SA 4.0 라이선스에 따라 이용할 수 있습니다.
하지만, 위키백과나 뉴스 기사 자체에 오류, 부정확한 정보, 또는 가짜 뉴스가 포함될 수 있으며, AI는 이러한 내용을 완벽하게 걸러내지 못할 수 있습니다.
따라서 제공되는 정보에 일부 오류나 편향이 있을 수 있으므로, 중요한 정보는 반드시 다른 출처를 통해 교차 검증하시기 바랍니다.

문의하기 : help@durumis.com