종만북 분할 정복 병합 정렬과 퀵 정렬 - 동작 원리와 시간 복잡도

병합 정렬 알고리즘은 수열을 절반으로 나눠 두개의 수열을 재귀 호출로 정렬한다. 쪼개서 정렬한 뒤 정렬된 배열을 합친다.

수열의 크기가 1이 될때까지 쪼개고 정렬한 다음 합친다. 절반으로 나누는 건 O(1), 병합은 O(n)

1. 반씩 나눈다.

2. 재귀 호출로 정렬한다.

3. 합친다.

반씩 나눌수록 문제의 수가 증가하지만 문제의 크기는 줄어 한 단계에서 모든 병합에 필요한 총 시간은 O(n)이다.

크기가 n인 배열을 크기가 1인 원소가 될 때까지 반으로 나누다보면 O(lgn)이 되고, 각 단계에 원소 수는 n으로 일정하므로

병합 정렬의 시간 복잡도는 O(nlgn)이 된다.

퀵 정렬 알고리즘은 병합 과정이 필요없다. pivot을 정해서 이보다 작은 건 왼쪽, 큰 건 오른쪽에 배치한다.

pivot을 만드려면 O(n)이 걸린다.

퀵 정렬은 pivot을 기준으로 배열을 나누지만 pivot 왼쪽과 오른쪽에 있는 원소의 수가 같거나 비슷함을 보장하지 못한다.

77 1 8 55 3 48 이 있다면 pivot 77을 기준으로 1 8 55 3 48 77이 되기 때문이다. 그러므로 최악의 경우 O(n^2)이며, 절반씩 잘 나눠진다면 병합 정렬과 동일한 O(nlgn)이다.