[알고리즘] 병합 정렬

병합 정렬

병합 정렬은 원소가 한 개가 될 때까지 계속해서 반으로 나누다가 다시 합쳐나가며 정렬을 하는 방식이다.

그리고 이 과정은 재귀적으로 구현된다.

 

 

 

아래의 숫자들을 오름차순으로 정렬해 보자

 

7 4 5 2 6 3 8 1

 

먼저 숫자들을 반으로 나눈다.

 

7 4 5 2  |  6 3 8 1 

 

그리고 나눠진 부분 중 첫번째를 한번 더 반으로 나눈다.

 

7 4 | 5 2 | 6 3 8 1 

 

마지막으로 한 번 더 나눠준다

 

7  | 4 | 5 2 | 6 3 8 1

 

이제 숫자가  7 과 4로 나뉘어져있다.

두 숫자를 병합 해보자.

 

단, 작은 숫자가 먼저 오도록한다

 

4 7 | 5 2 | 6 3 8 1

 

마찬가지로 5 ,2 역시 나눈 후 병합해보면

 

4 7  | 2 5 | 6 3 8 1

 

이제 4 7 | 2 5 부분을 병합

 

2 4 5 7  | 6 3 8 1 

 

이제 오른편의 6 3 8 1 역시 똑같은 과정을 적용시킨다.

 

2 4 5 7  | 1 3 6 8 

 

마지막으로 이제 양쪽 부분을 병합해주면

 

1 2 3 4 5 6 7 8 

 

 

 

쉽게 설명하자면 

 

 

0. 가운데를 기준으로 잡은후 반으로 나눠서( 왼쪽파트 , 오른쪽 파트)

1. 가장 작은부분으로 (숫자 1개)로 나누고 

   ex) 7 | 4 | 5 | 2 | 6 | 3 | 8 | 1  여기서 각 각 한칸은 이미 정렬된 상태로 볼수 있음 (원소한개가 한칸)

 

   1 - 2. 왼쪽 정렬, 오른쪽 정렬 후 병합해준다.

    ex) 4 7  

 

2.  4 | 7 두개의 원소를 기준으로 오른 쪽에 있는 원소 5 | 2에도 같은 작업을 수행 하고 

     ex) 2 5 

 

3. 두 원소를 병합    

 

전체적으로 나눈 왼쪽 파트와 오른쪽 파트가 병합되어  모든 원소들이 정렬될때까지 해주면 된다.