병합 정렬

🤔병합 정렬이란?

• 분할 정복 방식을 사용해 데이터를 분할하고 분할한 집합을 정렬하며 합치는 알고리즘이다.
• 시간 복잡도는 O(nlogn)이다.

👉 병합 정렬 수행 방식

병합 정렬 수행 방식

✔️ 병합 정렬 과정

1. 처음에는 가장 작은 데이터들을 분할한다.
2. 이어 2개씩 합치면서 오름차순으로 정렬한다.
3. 같은 순서로 반복하여 모든 수를 정렬할 수 있다.

🗝️2개의 그룹을 병합하는 과정

• 투 포인터 개념을 활용하여 2개의 배열을 병합 정렬할 수 있다.

2개의 그룹 병합 1

2개의 그룹 병합 2

• 왼쪽과 오른쪽의 값을 비교해서 작은 값을 결과 리스트에 추가하고, 인덱스를 오른쪽으로 1칸씩 이동시킨다.