합병정렬 (merge sort)

선택, 삽입, 버블정렬의 시간 복잡도는 이지만  합병정렬의 시간 복잡도는 으로

 

더 빠르게 정렬할 수 있다.  합병정렬의 절차를 그림으로 보게 되면 이렇게 된다.

 

이미지 출처 : https://m.blog.naver.com/PostView.nhn?blogId=itperson&logNo=220833815418&categoryNo=89&proxyReferer=http%3A%2F%2Fwww.google.co.kr%2Furl%3Fsa%3Di%26rct%3Dj%26q%3D%26esrc%3Ds%26source%3

Dimages%26cd%3D%26ved%3D2ahUKEwitzbP5upzgAhWXMt4KHYBVCpQQjRx6BAgBEAU%26url%3Dhttp%253A%252F%252Fm.blog.naver.com%252FPostView.nhn%253FblogId%

253Ditperson%2526logNo%253D220833815418%2526categoryNo%253D89%26psig%3DAOvVaw3rpROlljFASIsT3UnMnS3U%26ust%3D1549176655953059

 

 

배열의 처음(start) 과 마지막(end) 의 값을 2로 나눈 중간값(mid)을 정하여

 

처음 부터 중간까지(start~mid) 나누고, 중간의 다음 숫자부터 마지막 값까지(mid+1 ~ end)를 나눈다.

 

그 후에 두 부분으로 나눈 숫자들을 처음 인덱스부터 한개씩 비교하여 하나의 배열로 합친다.

 

합칠 때 서로를 비교 하여 합치기 때문에 정렬된 배열을 얻을 수 있다.

 

합병정렬은 중간값을 중심으로 나누고 비교하여 합치는 과정을 반복하기 때문에 재귀적으로 구현할 수 있다.

 

 

재귀함수를 빠져 나오기 위한 기저 조건 (Base Condition) 은 합병정렬을 하다보면 값이 1개가 남았을때, 즉 start

 

의 값과 end의 값이 같을 때 return을 해주게 된다.  위의 코드에서 기저 조건을 start 의 값이 end보다 같거나

 

크다(start >= end)라고 설정해 준 이유는 더 확실한 범위를 설정하기 위해서이다.

 

그 다음에는 start와 end의 값을 2로 나눠서 mid값에 넣어준 다음에 start~mid 와 mid+1~end까지 의 범위를 나눈

 

후에 처음 값부터 한개씩 비교하여 합쳐준다. 그것이 merging 함수 이다.

 

 

처음에 p에 s1과 q에 s2를 넣어 준 이유는 예를 들어

 

3  4  2  9  6        4  3  5  1  10

s1           e1      s2            e2

 

이렇게 두가지 범위로 나뉜 arr을 넘겨줬을 때 s1을 p에 넣고, s2를 q에 넣어 한개씩 차례로 비교하기 위해서 이다.

 

몇개의 숫자가 주어졌는지 모르기 때문에 while 문을 사용하여 반복한다. 언제까지 반복하는지 while의 조건문에

 

넣어 주어야 하는데 p와 q가 둘중에 하나라도 e1 과 e2의 범위를 벗어나게 되면 비교를 멈추고 채워진 배열에

 

이어서 남은 배열을 넣게 된다. temp 배열에 먼저 비교한 값들을 채운 다음에 temp에 채운 배열을 다시 기존의

 

arr 배열에 넣는다. 그러면 배열 arr이 정렬된다. 이렇게 해서 합병정렬 구현을 할 수 있다.

 

합병정렬 예시 문제를 풀어보자.

 

 

 

 

문제

---

서로 다른 n개의 정수가 주어질 때, 이를 합병정렬을 이용하여 오름차순으로 정렬하는 프로그램을 작성하시오.

 

입력

---

첫 번째 줄에 n이 주어진다. ( 1 ≤ n ≤ 100,000 ) 두번째 줄에 n개의 정수가 주어진다.  

출력

---

첫 번째 줄에 n개의 숫자를 합병정렬을 이용하여 오름차순으로 정렬한 결과를 출력한다.

 

예제 입력

10
2 5 3 4 8 7 -1 9 10 2

 

예제 출력

-1 2 2 3 4 5 7 8 9 10