현대의 컴퓨터 구조를 제시한 폰 노이만이 만든 정렬 알고리즘이다.

안정 정렬 (Stable Sort)에 속하며, 분할 정복 알고리즘의 하나이다.

<aside> 💡 분할 정복 알고리즘이란? 문제를 작은 2개의 문제로 분리하고 각각 해결한 다음 그 결과들을 모아서 원래의 문제를 해결하는 전략이다.

</aside>

하나의 리스트를 두개의 균등한 크기로 분할하고 분할된 부분 리스트를 정렬 한 다음, 두 개의 정렬된 부분 리스트를 합하여 전체가 정렬된 리스트로 되게하는 방법이다.

다음과 같은 단계들로 구성된다.

• 분할 (Divide) : 입력 배열을 같은 크기의 2개의 부분 배열로 분할한다.
• 정복 (Conquer) : 부분 배열을 정렬 한다. 부분 배열의 크기가 충분하지 않다면(1이하가 아니고 정렬되지 않은 배열이라면) 다시 분할을 적용 한다음 정복을 시도 한다.
• 결합 (Combine) : 정렬된 부분 배열들을 하나의 배열에 합병 한다. (각 부분 배열이 모두 정렬된 상태여야 이 시점으로 진입이 가능하다, 부분 배열이 정렬된 상태이니 부분 배열의 첫번째 인덱스끼리 비교해서 결합한다.)

추가적인 리스트 (결과를 저장할 리스트)가 필요하며

실제로 정렬이 이루어지는 시점은 각 부분배열을 합병(Merge)할때 이루어진다.

예시

배열에 20,10,12,20,25,13,15,22이 저장되어있다고 했을 시 오름차순 정렬과정이다.