5-1 Merge Sort 원리, 시간복잡도

Merge Sort 는 이름에서 풍겨오는 기운이, 뭔가를 합친다 라는 것 같습니다.

 

지금까지 일자로 나열된 형태의 데이터를 정렬하는 것과는 조금 다른 방식으로 정렬합니다.

 

일단 합치기 위해서는 쪼깨는? 작업 부터 합니다.

 

아래와 같이 생긴 애가 있습니다.

 

 

 

위의 아이를 절반씩 계속 쪼개줍니다.

 

자, 그 다음 정렬하면서 합쳐줍니다.

 

이렇게 합칠 수 있는데, 자 여기까지 보시면 저렇게 쪼개고 합치는 과정을 이해하셨을 것이라 생각합니다.

 

근데 이렇게 복잡한 방식으로 정렬을 왜 하는가? 에 대한 의문이 드실 수 있습니다.

 

그 이유는 이전에 봤던 정렬들보다 빠릅니다.

 

이 정렬의 시간복잡도를 보겠습니다.

 

일단 분할 / 합병 2가지로 나눕니다.

 

분할

 

아래와 같이 8개가 있는 리스트를 분할합니다.

 

 

크기가 8인 리스트를 분할했을 때, 오른쪽의 숫자처럼 3번의 과정이 있습니다.

 

크기가 16이라면, 4번의 과정이 있겠죠?

 

때문에, Big-O는 밑이 2인 O(log N) 입니다.

 

합병

 

그 다음 위에서처럼, 애들을 합쳐주는 과정에서의 시간복잡도는 O(N)입니다.

 

이 과정을 같이 해서 O(N log N) 입니다. 때문에 얘는 O(N^2)인 버블소트보다 빠릅니다.