합병 정렬 (Merge sort)

▶합병 정렬 (Merge sort)

---

분할 정복 기법으로 데이터를 정렬하는 방법이다.

가장 많이 쓰이는 정렬 기법이며, 크기 N의 데이터를 정렬해야하는 경우 N만큼의 공간이 더 필요하다.

데이터를 딱 한 번만 훑어서 정렬하기 위해서, 배열 arr의 데이터를 정렬하여 배열 tmp에 저장한 뒤 정렬되어있는 tmp의 데이터를 다시 arr에 반영하는 방법을 쓰기 때문이다.

1. 정렬할 N개의 데이터에 대해 범위를 계속해서 반으로 나눈다. (나뉘어진 범위의 데이터들을 덩어리 라고 표현하겠다.)

2. 덩어리의 크기가 1일 때부터 덩어리를 정렬하면서 합친다.

3. 그러면 크기 2의 정렬된 덩어리 하나가 만들어지게 되고, 그 덩어리는 또 다른 데이터 덩어리와 정렬하면서 합친다.

4. 그렇게 합쳐진 덩어리의 크기가 N이 될 때까지 수행하면 정렬이 완료된다.

▶시간 복잡도

---

최악의 경우 O(NlogN)의 시간이 걸리고, 평균적으로도 Θ(NlogN)이 걸린다.

데이터가 8개라고 가정했을 때 한 개의 데이터 덩어리부터 합치는 과정의 횟수는 3이다. (log8 = log2^3 = 3)

데이터 덩어리를 정렬하며 합치기 위해 8개의 데이터를 한 번씩만 확인하면 되므로 8*3 = 24번 연산을 수행한다.

N = 8일때, NlogN = 24임을 확인할 수 있다.

정렬을 위해 체크해야 할 범위가 계속해서 반으로 나누어지기 때문에 O(logN), 

나뉘어진 데이터를 합치는 과정에서 N개의 데이터를 한 번씩 확인하므로 O(N)이다.

따라서 전체적으로 O(logN)*O(N) = O(NlogN)의 시간이 걸린다.

▶소스 코드

---

[소스 코드 보기]