[정렬] 병합 정렬

✔ 병합 정렬

병합 정렬이란?

• 분할 정복 방식을 사용해 데이터를 분할하고 분할한 집합을 정렬한 후,
  이미 정렬된 부분 집합들을 효율적으로 병합해 전체를 정렬하는 방식
• 시간 복잡도의 평균값은 O(NlogN)
• 코딩 테스트의 정렬 관련 문제에서 자주 등장
• 특히 투 포인터를 사용하여 2개의 그룹을 병합하는 원리가 중요

병합 정렬 과정

1. 가장 작은 데이터 집합으로 분할
2. 2개씩 그룹을 병합하여 합치면서 정렬
   1. 투 포인터 개념을 사용하여 왼쪽, 오른쪽 그룹을 병합하며,
   2. 왼쪽 포인터와 오른쪽 포인터의 값을 비교하여 작은 값을 배열에 추가하고 포인터를 오른쪽으로 1칸 이동
   3. 만약 한 쪽 그룹의 데이터가 모두 배열에 추가될 경우, 다른 쪽 그룹에 남아있는 데이터를 그대로 모두 추가
3. 전체 데이터가 1개의 그룹으로 병합될 때까지 반복

 

Do it! 알고리즘 코딩테스트 with JAVA

https://inf.run/w9Tn