키베이루's diary

합병정렬은 분할 정복(Divide and Conquer)의 알고리즘의 하나이다. 합병정렬의 핵심은 3가지이다. Divide : 입력된 배열을 절반 씩 계속 나눈다. void merge_sort(int left, int right, int[] arr) // 나눠! { // 왼쪽이 오른쪽보다 작을때만 실행하고 // 왼쪽이 오른쪽과 같아지거나 커질경우 재귀가 풀리면서 merge가 실행된다. if (left < right) { int mid = (left + right) / 2; // 처음과 끝을 반으로 갈라서 (처음 ~ 중간) / (중간 ~ 끝) merge_sort(left, mid, arr); // 처음부터 중간까지 나눈다 merge_sort(mid + 1, right, arr); // 중간부터 마지막 까지..