머지 정렬은 위 내용을 보면 쉽게 이해할 수 있을 것 같다.

말 그대로 배열을 그룹화 하면서 모두 하나로 쪼갠 다음에 그룹별로 값을 비교하면서 하나의 배열로 합치면서 정렬이 진행되는 방식이다.

위 그림의 과정 전체는 아래와 같다.

그래서 합병 정렬의 시간 복잡도는 n개의 데이터를 가지고 logN단계를 거치기 때문에 O(NlogN)이 된다. 퀵 정렬은 피봇을 어떻게 선택하느냐에 따라 최악의 시간 복잡도가 O(N^2)가 되지만 병합 정렬은 항상 리스트를 절반으로 나누기 때문에 O(NlogN)의 시간 복잡도를 보장한다.

자바스크립트로 짠 Merge Sort 코드는 아래 URL에서 확인 할 수 있다.

GitHub : Merge Sort

Merge Sort vs Quick Sort

퀵 정렬(Quick Sort)은 데이터의 분포에 따라 최악의 경우 O(n2)의 시간 복잡도를 갖고 있고, 평균 시간 복잡도는 O(nlogn)의 시간 복잡도를 가지고 있다. 불안정한(UnStable) 정렬이다.

병합 정렬(Merge Sort)은 모든 경우의 수에서 O(nlogn)의 시간 복잡도를 보장하기 때문에 안정적인(stable) 정렬이다.

하지만 데이터가 배열로 구성된 경우 임시 배열이 필요하므로 추가 공간이 필요하다. 그래서 추가 공간을 사용하므로 제자리 정렬이 아니다. 빅 데이터인 경우에는 메모리 낭비가 발생할 수 있다.

그래서 메모리 공간이 추가적으로 더 필요없는 In-place 정렬인 퀵 정렬(Quick Sort)을 많이 사용하게 되었다.

• In-place 알고리즘
  원소들의 개수에 비해서 충분히 무시할 만한 저장 공간만을 더 사용하는 정렬 알고리즘. 아마 학교에서는 제자리성(혹은 제자리 정렬)과 같은 이름으로 들어봤을 수도 있겠다.

• Merge Sort 공부 자료