병합정렬

병합정렬의 개요

병합정렬의 정의

존 폰 노이만이 개발한 배열을 같은 크기로 분할하여 이를 다시 조합하는 과정을 통해 데이터를 정렬하는 알고리즘

병합정렬의 특징

• 시간 성능: 평균 및 최악의 성능에도 O(nlog n)을 보장
• 공간 성능: 처리 결과 저장을 위해 2n 만큼의 메모리 할당 필요
• Linked List 정렬에 최적화

병합정렬의 의사코드

병합정렬의 과정