[ Divide and Conquer ] Recursive Merge Sort

Divide and Conquer

• 입력을 나누어,
• 더 작은 문제를 풀고
• 작은 문제들의 답을 조합하여
• 전체 문제듸 답을 만든다.

아주 작은 문제는 어쨌는 풀 수 있다. 

 

수 하나가 주어질 때도, 값이 큰지 작은지에 따라 다르다.

어떤 문제든지 간에 size라는 것이 있고, 문제를 작게 나누어서 작은 문제를 풀고 이러한 답을 큰 문제를 푼다.

이러한 작은 문제들은 재귀를 사용할 수 있다. 

 

Recursive Merge Sort

n개가 있다면, n/2로 나누고, 그것을 또 나누고.. 이를 반복하여 하나씩 남을 때까지 나눈다.

이를 나누어서 목적지 배열에 Merge Alg를 사용해서 sorting을 한다. 

Merge Alg -> O(n) 왼쪽부터 하나씩 보면서 움직이는 것이므로 n번 걸린다. 

 

https://m-in-zu.tistory.com/33

Merge Sort

 

양쪽 갯수가 다를 수도 있다. (어딘가에서 나누어떨어지지 않을 수도 있다.)

Assum n=\(2^k\), k ≥ 0

ex) 10개가 주어진다면 16으로 늘린다. 뒤에 무한대인 숫자를 6개 넣는다. 이래도 최대 2배 늘어나므로 O(n)에서 크게 벗어나지 않는다.

따라서 T(n) = 2T(n/2) + n

int sort(int a[], int n){
    int h;
    int b[n];
    h = n/2'
    
    //copy a[] to b[]
    sort(b,h);
    sort(b+h, n-h);
    
    //Merge two halves in b to a
    return ;

전체 걸리는 시간은 T(n)이다.

n/2짜리가 현재 두개 존재한다. (재귀로) 

해당 재귀 함수를 제외하고 나머지 걸리는 시간을 넓은 의미로는 그냥 n, 정확히 모르는 상수 c의 곱이다.

T(n) = 2(2T(n/4) +(n/2)) + n = .... log n 번 내려가면 = O(nlogn)이다. 

T(n) = a nlogn + b

a nlogn + b =2(a*n/2 + log n/2 + b) + n = an(logn -1) + 2b + n = anlogn - an +2b + a

b = 0, a = 1

따라서 T(n) = nlogn 

 

Merge Sort is good enough under O()

But allocating a new array is unavoidable and expensive

*어디까지가 sort? 특수한 경우에 빠른 sorting 들이 있다. 

Sorting에서 근본적으로 필요한 것은 비교이다 - Companison Model

 

O(N log N)보다 빠르게 allocating 할 수 없다. 

1,2,3,4,5 ... n 이 그저 섞여서 들어온거다. 

가능한 입력은 n!가지

비교를 하면, n! 들을 반으로 계속 나누어서 log n 만큼 내려가므로 log(n!)은 O(nlogn)과 비슷하다. 

 

n이 커지면 잘 쓰지 않는다. 배열을 추가로 할당하여 순서를 만들기 때문에 메모리가 2배가 되기 때문에 n이 커지면 비효율적이다.