병합 정렬(merge sort)는 크게 세 가지 단계로 이루어진다.
분할(Divide): 입력 배열을 같은 크기의 2개의 부분 배열로 분할한다.
정복(Conquer): 부분 배열을 정렬한다. 부분 배열의 크기가 충분히 작지 않으면 순환 호출 을 이용하여 다시 분할 정복 방법을 적용한다.
결합(Combine): 정렬된 부분 배열들을 하나의 배열에 합병한다.
먼저 배열을 크기가 하나가 될 때까지 쪼갠다. 그리고 두 개의 배열씩 정렬하며 병합해서 마지막 병합 배열은 정렬된 배열이 되게 한다.
병합 정렬은 두 개로 분할되는 과정에서 재귀가 되어 수행 시간을 계산하면
T(n) = O(nlogn)의 수행시간이 나온다. (최악,평균,최선의 상황 동일)
이것은 오름차순으로 짜본 병합 정렬 코드이다.
mergeSort 2번의 재귀로 계속해서 쪼개지는 걸 알 수 있고
밑에서 부터 merge가 차례대로 실행 되며 병합되는 것을 알 수 있다.
그에 따른 실행 화면인데 역시 정상적으로 정렬이 되었음을 알 수 있다
병합 정렬의 과정
코드를 짜고 종이에 써 보아도 직접 실행되는 과정을 눈으로 보고 싶어서 중간 과정에 printf로 어떤 식으로 재귀가 되고 있는지 확인하였다.
그래서 merge에 printf를 적어서 병합이 될 때마다 그 과정과 해당 인덱스에 어떤 값이 있는지 출력되도록 했다.
병합 정렬의 세부화
먼저 궁금했던 것은 arr(원본)배열의 값이 변화는 과정이다 재귀를 거듭하면서 해당 인덱스에 새로운 정렬 값들이 대입 되는 것을 알 수 있다.
이로써 해당 재귀가 어떤 식으로 돌아가는지 공부할 수 있었다.
병합 정렬 내림차순
추가로 이번 과제인 병합 정렬을 내림차순으로 정렬 해보았다.
원래 했던 병합 정렬에서 부등호만 수정한다면 아주 쉽게 내림차순으로 정렬할 수 있었다.
더 크다면 0번째 인덱스 부터 담으면 되는 것이다.
