Merge Sort(병합 정렬)

이 글은 인프런의 영리한 프로그래밍을 위한 알고리즘 강좌를 듣고 정리한 내용입니다.

Merge Sort(병합 정렬)

분할 정복법(Merge Sort, Quick Sort)

분할 : 해결하고자 하는 문제를 작은 크기의 동일한 문제들로 분할

정복 : 각각의 작은 문제를 순환적으로 해결

합병 : 작은 문제의 해를 합하여(Merge) 원래 문제에 대한 해를 구함

1. 리스트의 길이가 0 또는 1이면 이미 정렬된 것으로 본다. 그렇지 않은 경우

2. 정렬되지 않은 리스트를 절반으로 잘라 비슷한 크기의 두 부분 리스트로 나눈다.

3. 각 부분의 리스트를 재귀적으로 합병 정렬을 이용해 정렬한다.

4. 두 부분의 리스트를 다시 하나의 정렬된 리스트로 합병한다.

의사코드

Merge Sort(A[], p, r) {    // 배열 A[p...r]을 정렬한다.
if(p<r) then {
q <- (p+q)/2;    ------------------------------- ①
mergesort(A, p, q);    ------------------------- ②
mergesort(A, q+1, r);    ----------------------- ③
merge(A, p, q, r);    -------------------------- ④
}
}
merge(A[], p, q, r) {
정렬되어 있는 두 배열 A[p...q]와 A[q+1...r]을 합하여
정렬된 하나의 배열 A[p...r]을 만든다.
}

시간복잡도

T(n) = O(nlogn)

소스 코드(Java)