병합 정렬

개요

우선 전체 요소를 각 부분 집합의 크기가 1개가 될 때까지 반절로 재귀적으로 쪼갠다.
그리고 쪼개진 부분 집합들을 역순으로 조립해나간다.
이 때, 조립은 2 개씩 진행하며 2개를 조립할 때 각 부분 집합을 큐로 취급하여
두 큐의 맨 앞 요소 중 가장 작은 값을 선택하고 pop하며 차곡차곡 조립한다.
이 과정을 재귀적으로 진행하면 결국 전체적으로 정렬이 된다.

---

복잡도

	최악	평균	최소
Big O 표기법	O(nlogn)	O(nlogn)	O(nlogn)

---

알고리즘 절차

1. 합병 정렬을 준비하기 위해 정렬할 배열[arr]와 크기가 똑같은 빈 배열[tmp]을 생성한다.
2. 정가운데 요소를 기준으로 arr를 반으로 잘라내고 각 부분을 재귀적으로 합병 정렬한다. 
   이 때, 정렬은 후위 순회를 하며 진행한다.
3. 실제 정렬 방법은 다음과 같다.
   1. 앞 부분[A]을 tmp에 그대로 복사한다.
   2. 뒷 부분[B]은 arr에 그대로 남겨둔다.
   3. A와 B의 앞 부분부터 비교하며 더 작은 값을 실제 arr에 차곡차곡 적재해나간다.
   4. A와 B의 모든 요소가 arr에 적재될 때까지 진행한다.

---

자바 코드

class Merge {
    public static void main(String[] args) {
        int[] testCase1 = {1, 26, 9, 67,653,452,2,3,46,87,356543};

        int[] tmp = new int[testCase1.length];
        mergeSort(testCase1, tmp, 0, testCase1.length-1);

        for (int item : testCase1) {
            System.out.println(item);
        }
    }
    
    static void mergeSort(int[] arr, int[] tmp, int low, int high) {
        if(high==low) return ;
        
        int mid = (int) ((high+low) / 2);
        
        mergeSort(arr, tmp, low, mid);
        mergeSort(arr, tmp, mid+1, high);
        
        merge(arr, tmp, low, mid, high);
    }
    
    static void merge(int[] arr, int[] tmp, int low, int mid, int high) {
        for(int i=low; i<=mid; i++) {
            tmp[i] = arr[i];
        }
        
        int idxFront = low;
        int idxBack = mid+1;
        int idxArr = low;
        while(idxFront <= mid && idxBack <= high) {
            if(tmp[idxFront] < arr[idxBack]) {
                arr[idxArr++] = tmp[idxFront++];
            } else {
                arr[idxArr++] = arr[idxBack++];
            }
        }
        
        while(idxFront <= mid) {
            arr[idxArr++] = tmp[idxFront++];
        }
    }
}