Es la vida~

Merge sort(병합 정렬)는 원소들 간의 비교를 통해 정렬하는 비교 기반 정렬 알고리즘이다.

원소들 중 같은 값이 있는 경우 정렬 후에도 순서가 유지된다.

정렬의 과정은 분할 -> 정복 -> 합병(결합) 의 순서로 이루어진다.

합병 정렬은 다음과 같이 작동한다.

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

시간 복잡도는 N 개의 데이터를 정렬할 때를 기준으로 O(N * logN)이다.

Merge sort의 정렬과정을 예를 들면 아래와 같다.

처음에 초기배열 상태에서 가운데를 기준으로 반으로 나누어 분할 상태가 된다.

이후 분할된 앞쪽과 뒷쪽을 각각 정렬(정복이라 칭함) 수행 후 다시 하나의 배열로 만드는 결합 과정을 수행하는 방식이다.

아래는 위키피디아에 나온 병합 정렬 과정의 수행 절차를 나타낸 것이다.