[Algorithm]합병정렬

합병정렬의 흐름 by 위키백과

합병정렬은 O(n*logn)의 시간복잡도를 가진 선택, 삽입, 버블정렬보다는 빠른 정렬방식이다.

합병정렬은 배열의 모든 원소를 하나로 떼어낸 후에 원소 하나하나 대소를 비교하여 작은 수를 앞으로 오게 하는 방식이다. 결국 합병정렬의 흐름은 모든 원소를 떨어뜨린 후 하나둘 합치는 식으로 이루어진다.

(브런치는 코드 올리는게 불편하여 부득이하게 스크린샷으로 대체했다)

이 부분은 먼저 배열의 원소를 떼어내는 작업이다. 

재귀이기 때문에 가장 먼저 탈출 조건을 설정해주고, left, right에 원소를 넣고 재귀를 통해 원소가 하나가 될 때 까지 떼어내는 작업을 반복한다.

그 다음은 하나씩 떼어낸 원소의 대소를 비교하여 합쳐줄 차례다. left배열의 원소와 right배열의 원소의 수를 비교하여 arr배열의 0번째부터 채워간다.

*맨 위에 위키백과 자료를 꼭 참고하여 이해하자

* 재귀의 흐름을 유의하여 코드를 이해하자

대소를 비교하여 수를 넣고난 후에는 대소를 비교할 수 없는 경우

-left나 right의 배열에만 수가 있을 때-

 남은 수를 배열에 넣어줘야 한다.

이 때 남은 수는 이미 정렬이 되어 있는 수 이므로 그대로 배열에 넣어주면 된다.