병합 정렬(Merge Sort) 이란?

병합 정렬은 효율적인 정렬 알고리즘 중 하나로, 분할 정복(Divide and Conquer) 방식을 사용하는 것이 특징이다.

병합 정렬은 다음과 같은 세 단계로 동작한다.

  1. 분할(Divide)

: 정렬할 리스트를 두 개의 균등한 크기(또는 거의 균등한)의 서브 리스트로 분할한다.

이 과정은 서브 리스트의 크기가 1이 될때까지 재귀적으로 반복된다.

크기가 1인 리스트는 이미 정렬되었다고 간주한다.

  1. 정복(Conquer)

: 분할된 서브 리스트들을 각각 재귀적으로 정렬한다.

  1. 결합(Combine) / 병합(Merge)

: 정렬된 두 개의 서브 리스트를 다시 하나의 정렬된 리스트로 병합한다.

이 병합 과정이 병합 정렬의 핵심이다.

주요 특징