[알고리즘] 합병 정렬(Merge Sort)

---

합병 정렬이란

---

분할 정복 알고리즘에서 부분문제의 수와 부분문제의 크기에 따라 분류된 정렬 알고리즘이 몇 개 있다.

그 중 하나가 합병/병합 정렬이다.

 

합병 정렬은 문제가 2개로 분할되고, 부분문제의 크기가 1/2로 감소하는 알고리즘이다. 즉 n개의 숫자들을 n/2개 씩 2개의 부분문제로 분할하고, 각각의 부분문제를 정렬한 후, 병합한다. 

 

합병(merge)란 2개의 정렬된 숫자들을 1개의 정렬된 숫자들로 합치는 것이다. 

 

 

알고리즘)

mergeSort(A, p, q)
input: A[p] ~ A[q] 
output: 정렬된 A[p] ~ A[q]

1. if( p < q ){
2.	  k = (p+q)/2        //k는 배열의 중간을 구함
3.    mergeSort(A, p, k) // 앞부분 배열
4.    mergeSort(A, k+1, q) //뒷부분 배열
5.    A[p] ~ A[k] 와 A[k+1] ~ A[q]를 병합한다.
 }