병합 정렬(Merge Sort)

병합 정렬(Merge Sort)

• 합병 정렬이라고도 부르며, 분할 정복 방법을 통해 구현된다.
• 빠른 정렬로 분류되며, 퀵소트와 함께 많이 언급되는 정렬 방식이다.
• 퀵소트와는 반대로 안정 정렬에 속한다.
• 요소는 분리하고 다시 합병시키면서 정렬해나가는 방식으로, 분리하는 방식은 퀵정렬과 유사하다.
  • Quick Sort : 피벗을 통해 정렬 → 분리
  • Merge Sort : 분리되지 않을 때 까지 분리 → 정렬
• Merge Sort는 순차적인 비교로 정렬을 진행하므로, LinkedList의 정렬이 필요할 때 사용하면 효율적이다.

시간복잡도

• O(nlogn)

공간복잡도

• 병합 정렬이 입력 배열에서 분할 및 정복 방식으로 작동하고 정렬된 후 하위 배열이 다시 병합되기 때문에 공간복잡도는 O(n)이다.

장점

• 병합 정렬은 동일한 값을 가진 요소의 상대적 순서를 유지하므로 안정적인 정렬 알고리즘이며, 대규모 데이터 세트에 효율적이다.
• 병합 정렬은 시간 복잡도가 O(nlogn)이므로 요소 수가 많은 경우에도 성능이 우수하여, 외부 정렬에 적합하다.
• 병합 정렬은 효율적인 병합 기술을 활용하여 외부 데이터 정렬을 처리할 수 있다.

단점

• 병합 정렬은 임시 하위 배열을 저장하기 위해 추가 공간이 필요하므로 메모리가 제한된 환경에는 적합하지 않으며, 작은 데이터 집합에는 가장 효율적이지 않다.
• 병합 정렬은 재귀 호출 및 병합 프로세스에 대한 오버헤드로 인해 작은 데이터 세트의 경우 삽입 정렬 또는 버블 정렬과 같은 다른 정렬 알고리즘보다 효율성이 떨어진다.