How it works?

병합 정렬은 분할, 정복, 결합의 세 단계를 따릅니다.

단계별 과정:

1. 분할: 배열을 두 개의 반으로 나눕니다.
2. 정복: 각 반을 재귀적으로 정렬합니다. 요소가 하나(또는 없는)인 조각은 이미 정렬된 것이므로 재귀가 거기서 멈춥니다.
3. 결합: 정렬된 두 반을 하나의 정렬된 배열로 병합합니다.

[6, 3, 8, 5]에 대한 예시:

• [6, 3]과 [8, 5]로 분할
• 다시 분할: [6], [3], [8], [5]
• [6]과 [3]을 [3, 6]으로 병합
• [8]과 [5]를 [5, 8]로 병합
• [3, 6]과 [5, 8]을 [3, 5, 6, 8]로 병합