[알고리즘] 병합 정렬 (merge sort) 쉽게 이해하기!

병합 정렬 (merge sort)

 

병합 정렬, 합병 정렬 둘 다 같은 말이다.. 

 

병합 정렬은 일단 배열이 더 이상 쪼개지지 않을 때까지  절반으로 계속 쪼갠다.

 

그리고 조각을 2개씩 묶어 각각을 크기순으로 배열하고

 

또 그 조각을 2개씩 묶어 크기순으로 배열하는 식이다. 

 

 

예를 들어, [4, 1, 8, 6, 7, 2, 3, 5] 가 있으면 이런 식으로

 

원소가 하나 하나 뜯어질 때까지 나눈다.

 

 

그리고 더 이상 뜯어지지 않을 정도로 나뉘어졌다면,

 

이제 반대로 하나 하나 붙이는데, 이 때 정렬을 같이 해준다.

 

 

이게 끝이다..!

 

알고리즘을 이해하는 것 자체는 그리 어렵지 않을 것이다.

 

 

분할 정복 알고리즘

 

 

하지만 지금까지 설명했던 알고리즘과는 달리  굳이 이렇게 해야하나?

 

싶을 수도 있을 것 같아 설명을 덧붙이자면,

 

배열의 크기가 커지면 이런 분할 정복 알고리즘이 더 효율적이다.

 

 

분할 정복 알고리즘이란, 

 

큰 배열 하나를 작은 배열 여러 개로 쪼갠 뒤,

 

하나 하나 맞추어 해결해 나가는 알고리즘을 말한다.

 

분할 정렬 알고리즘의 예시

 

1부터 100까지 적힌 카드가 흐트러져 있을 때

 

우리가 1, 2, 3, 4 .. 순으로 카드를 하나 하나 찾지 않고

 

먼저 10의 자리대로 카드를 나눈 뒤,

 

나누어진 10개의 뭉치를 다시 순서대로 배치하는 것 역시

 

분할 정렬 알고리즘을 사용한 것이라고 볼 수 있다.

 

 

분할 정렬 알고리즘이 효율적인 이유

 

왜 이게 효율적인지 아직 와닿지 않는다면 

 

아래 예시가 도움이 될 것이다. 

 

 

8명이 같이 가위바위보를 할 때

 

계속 승부가 나지 않으면 

 

4명 4명 나누어서 가위바위보를 한다. 

 

 

왜? 4명이 가위바위보를 해서 결과가 나는 게

 

8명이 가위바위보를 계속 하는 것보다 빠르기 때문이다.

 

또한, 그렇게 4명 4명 나눈 것보다

 

2명 2명 2명 2명 이렇게 네 팀으로 가위바위보를 하는 것이 더 빠르다.

 

따라서 작은 조각으로 나누어 먼저 해결하는 방식은

 

시간을 줄여주고 효율적이라고 할 수 있다.