Merge Sort

수 많은 종류의 정렬 알고리즘이 존재한다. 하지만 비교적 많이 사용되는 기법은 병합정렬(Merge Sort)과 퀵정렬(Quick Sort) 정도다.

정렬 알고리즘 시간 복잡도 비교

• 병합정렬은 Best, Average, Worst case 모두 O(nlogn)을 보장한다. 또한 중요한 특징중의 하나는 stable sort라는 점이다. Stable sort는 값이 같은 원소가 있을 때, 기존의 순서를 유지하는 정렬을 말한다. 즉 기존의 배열에서 뒤의 요소가 항상 작아야만 앞의 원소로 배치되어 값이 같은 경우 기존의 순서를 유지하는 것을 말한다. 즉, 1로만 이루어진 배열이 있다고 한다면 같은 1로 느껴질 수 있지만, 기존의 순서를 유지한다는 의미이다.
  1, 1, 1 -> 1, 1, 1
• 퀵 정렬은 Best, Average O(nlogn)을, worst case는 O(n^2) 시간 복잡도를 가진다. worst case가 나오는 경우는 배열이 정렬된 형태를 가질 때이다. 하지만, 경험적으로 quick sort는 평균적으로 매우 빠른 작동 시간을 보여준다. 이에 따라 많이 사용한다. 다만, unstable sort라는 점을 유념해 두어야 한다.

Merge sort의 특징에 대해서 참고할 만한 사이트
Merge sort 특징

아래 사이트에 가져온 내용으로, 상세한 비교가 잘 되어있다.
정렬 알고리즘 시간 복잡도 비교

아래의 문제에서 merge sort의 장점을 확인할 수 있다.
문제의 해결 자료구조로 Segment tree와 merge sort를 사용할 수 있는데, 실행시간이 꽤 많은 차이를 보여준다. 물론, merge sort(400ms)는 C++로 짜고, Segment tree(4000ms)는 python으로 짰음에도 말이다.