바른생활해보자

합병 정렬 (Merge Sort) 입력값을 $1/2$로 분할하여 부분문제 크기를 감소시키는 분할 정복 알고리즘이다. N개의 숫자의 배열을 N/2개씩 분할하고 재귀적 합병 정렬 후, 2개의 정렬된 부분을 합병하여 정렬한다. 즉, 합병 과정이 문제를 정복하는 것이다. 시간복잡도 합병 정렬은 분할 후 합병이 일어난다. 먼저 분할은 배열을 더이상 나눌서 없을때까지 2개의 배열로 나누는 재귀함수를 호출하는 것으로 O(1)의 시간이 걸린다. 이후 합병으로 넘어가면 2개의 정렬된 배열 A(크기 m개)와 B(크기n개)를 받으면 최대 비교 횟수는 (m+n-1)번이다. 합병시 두개의 숫자를 한번씩 비교할때, 더 작은 수가 결과 배열인 C에 저장된다. 따라서 배열 C는 A와 B의 모든 수(m+n)의 숫자들이 저장되나, 가장..