합병 정렬 알고리즘

arr=[5, 4, 6, 8, 2, 3, 1, 7, 9, 0]

 

위 배열을 합병 정렬을 사용해 오름차순으로 정렬 해보자.

 

합병 정렬은 mid값으로 계속해서 분할해 각각을 오름차순으로 정렬한 후 병합하는 방법이다.

 

일단 전체 배열의 mid값 4를 기준으로 나눈다.(4.5같은 경우엔 버림해 4로 계산한다)

[5, 4, 6, 8, 2]와 [ 3, 1, 7, 9, 0]로 나눈다.

 

[5, 4, 6, 8, 2]도 Mid값을 이용해 나눈다.

 

[5, 4, 6]와 [8, 2]로 나눈다.

이 또한 [5, 4],[6]와[8],[2]로 나뉜다.

다시 [5],[4]와[6]와[8],[2]로 나뉘어진다.

[5],[4],[6]을 합병하면 [4, 5, 6]이 된다.

또 [8],[2]를 합병해 [2, 8]을 만든 후

[4, 5, 6]과 [2, 8]을 합병한다.

그러면 [2, 4, 5, 6, 8]이 된다

 

오른쪽 [ 3, 1, 7, 9, 0]도 마찬가지로

[3, 1, 7]과 [9, 0]이 된다.

똑같이 [3, 1]과[7]이 되고

다시 [3],[1]과[7]이 된다. 이를 병합하면 [1, 3, 7]이 되고

[9],[0]을 병합하면 [0, 9]가 된다.

 

이제 [1, 3, 7]과 [0, 9]를 합병한다.

[0, 1, 3, 7, 9]가 나오고

마지막으로 [2, 4, 5, 6, 8]과 합병하면

[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]가 나온다.