문서 편집 권한이 없습니다. 다음 이유를 확인해주세요: 요청한 명령은 다음 권한을 가진 사용자에게 제한됩니다: 사용자. 문서의 원본을 보거나 복사할 수 있습니다. [[분류:정렬]] [[파일:Merge Sort.gif|섬네일|가운데]] == 개요 == 폰 노인만에 의해서 개발된 Merge Sort 는 안정적으로 nlogn 만에 배열을 정렬할 수 있도록 해준다. 기본 원리는 배열을 일단 최소 단위까지 쪼갠후 최소 단위부터 조금씩 맏추면서 올라가는 방식이다. [[분할 정복 알고리즘]]의 좋은 예시이다. 성능은 [[퀵 정렬]]보다 전반적으로 뒤떨어지고, 데이터 크기만한 메모리가 더 필요하지만 최대의 장점은 데이터의 상태에 별 영향을 받지 않는다는 점이다. 힙이나 퀵의 경우에는 배열 A[25]=100, A[33]=100인 정수형 배열을 정렬한다고 할 때, 33번째에 있던 100이 25번째에 있던 100보다 앞으로 오는 경우가 생길 수 있다. 그에 반해서 병합정렬은 그런 거 없다. 정렬되어 있는 두 배열을 합집합할 때 이 알고리즘의 마지막 단계만을 이용하면 가장 빠르게 정렬된 상태로 합칠 수 있다. == 알고리즘 == 합병 정렬은 다음과 같이 작동한다. # 리스트의 길이가 1 이하이면 이미 정렬된 것으로 본다. 그렇지 않은 경우에는 # 분할(divide) : 정렬되지 않은 리스트를 절반으로 잘라 비슷한 크기의 두 부분 리스트로 나눈다. # 정복(conquer) : 각 부분 리스트를 재귀적으로 합병 정렬을 이용해 정렬한다. # 결합(combine) : 두 부분 리스트를 다시 하나의 정렬된 리스트로 합병한다. 이때 정렬 결과가 임시배열에 저장된다. # 복사(copy) : 임시 배열에 저장된 결과를 원래 배열에 복사한다. Merge sort 문서로 돌아갑니다.