Ahn9807: 새 문서: 분류:정렬 가운데 == 개요 == 폰 노인만에 의해서 개발된 Merge Sort 는 안정적으로 nlogn 만에 배열을 정렬할 수 있도록 해준다. 기본 원리는 배열을 일단 최소 단위까지 쪼갠후 최소 단위부터 조금씩 맏추면서 올라가는 방식이다. 분할 정복 알고리즘의 좋은 예시이다. 성능은 퀵 정렬보다 전반적으로 뒤떨어지고, 데이터 크기만한 메...

2023-03-21T03:32:44Z

새 문서: 분류:정렬 섬네일|가운데 == 개요 == 폰 노인만에 의해서 개발된 Merge Sort 는 안정적으로 nlogn 만에 배열을 정렬할 수 있도록 해준다. 기본 원리는 배열을 일단 최소 단위까지 쪼갠후 최소 단위부터 조금씩 맏추면서 올라가는 방식이다. 분할 정복 알고리즘의 좋은 예시이다. 성능은 퀵 정렬보다 전반적으로 뒤떨어지고, 데이터 크기만한 메...

새 문서

[[분류:정렬]]
[[파일:Merge Sort.gif|섬네일|가운데]]

== 개요 ==
폰 노인만에 의해서 개발된 Merge Sort 는 안정적으로 nlogn 만에 배열을 정렬할 수 있도록 해준다. 기본 원리는 배열을 일단 최소 단위까지 쪼갠후 최소 단위부터 조금씩 맏추면서 올라가는 방식이다. [[분할 정복 알고리즘]]의 좋은 예시이다. 성능은 [[퀵 정렬]]보다 전반적으로 뒤떨어지고, 데이터 크기만한 메모리가 더 필요하지만 최대의 장점은 데이터의 상태에 별 영향을 받지 않는다는 점이다. 힙이나 퀵의 경우에는 배열 A[25]=100, A[33]=100인 정수형 배열을 정렬한다고 할 때, 33번째에 있던 100이 25번째에 있던 100보다 앞으로 오는 경우가 생길 수 있다. 그에 반해서 병합정렬은 그런 거 없다. 정렬되어 있는 두 배열을 합집합할 때 이 알고리즘의 마지막 단계만을 이용하면 가장 빠르게 정렬된 상태로 합칠 수 있다.

== 알고리즘 ==
합병 정렬은 다음과 같이 작동한다.
# 리스트의 길이가 1 이하이면 이미 정렬된 것으로 본다. 그렇지 않은 경우에는
# 분할(divide) : 정렬되지 않은 리스트를 절반으로 잘라 비슷한 크기의 두 부분 리스트로 나눈다.
# 정복(conquer) : 각 부분 리스트를 재귀적으로 합병 정렬을 이용해 정렬한다.
# 결합(combine) : 두 부분 리스트를 다시 하나의 정렬된 리스트로 합병한다. 이때 정렬 결과가 임시배열에 저장된다.
# 복사(copy) : 임시 배열에 저장된 결과를 원래 배열에 복사한다.

Merge sort - 편집 역사