1. 분할: 주어진 배열을 반으로 나눕니다. 이 과정은 배열의 중간 지점을 찾고, 그를 기준으로 왼쪽과 오른쪽으로 배열을 나누는 과정으로 이루어집니다.

2. 정복: 나눠진 배열들을 재귀적으로 정렬합니다. 이는 배열의 크기가 1이 될 때까지 계속됩니다.

3. 병합: 정렬된 하위 배열들을 하나로 병합합니다. 이때 정렬된 순서를 유지하면서 병합이 이루어집니다. 정렬된 두 배열을 비교하여 더 작은 항목을 새 배열에 삽입하는 방식으로 병합됩니다.

이러한 단계를 반복하면서 배열이 계속해서 반으로 나뉘고 정렬되어 최종적으로 전체 배열이 정렬됩니다. 병합 정렬 알고리즘은 안정적이며 대규모 데이터셋에 대해 효율적으로 동작하는 장점이 있습니다.

이와 같은 병합 정렬 알고리즘은 Java를 비롯한 여러 프로그래밍 언어에서 일반적으로 사용되며, 대부분의 정렬 라이브러리에서도 활용됩니다.

참고 문헌:

• Introduction to Algorithms, Cormen et al. (서지 정보 추가)