병합 정렬(Merge Sort)

키 포인트!!

일단은 반으로 나누고 나중에 합친다!

 

병합정렬은 퀵정렬가 달라 피벗 값이 없고 항상 반으로 나누는 특징이 있다

이렇게 반으로 쪼개는 단계때문에 O(Nlog N)이 된다. 

또한 퀵 정렬과 다르게 정확히 반으로만 나누기 때문에 NlogN이 보장이 된다.

 

7  4  5  8  6  3  10  9 이런 배열이 있다고 가정하자

이것을 이제 2의 배수의 개수만큼 합친다. 근데 그때 오름차순으로 정렬하면서 합친다 

2^1 :  4,7     5,8     3,6     9,10

2^2 :  4,5,7,8      3,6,9,10 

2^3 :  3,4,5,6,7,8,9,10 

 

이렇게 2의 승으로 진행되기 때문에  많은 데이터를 다룰 수가 있고 이 때문에 시간복잡도가 logN이다. 

위의 표를 사각형으로보면 가로는 N이고 높이는 logN이다 따라서 총 시간 복잡도가 O(N*logN)이다

 

가장 중요하게 기억해야 하는 것은 합치는 그 순간에 정렬을 수행하는 것이다.

 

 

이 배열을 병합정렬을 한다고 가정하자

여기서의 수행 순서는

1. 현재 위치의 i와 j를 비교해 작은 수를 k에 넣는다. 

2. 그러면 j+1로 이동해 6과 8을 비교한다. 더 작은 6이 k+1에 들어간다

3. i+1로 이동해 j+1과 비교해 7이 k+2에 들어간다

4. 나머지 8이 마지막으로 들어간다

 

여기서 i가 m 7과 5사이가 middle그리고 8이 end이다. 

코드를 통해서 보면 다음과 같다 

반복학습을 통해 완전히 이해해보쟈!