Merge sort

 

 

출처 : https://en.wikipedia.org/wiki/Merge_sort 

 

 

 

 

 

public static void main(String[] args) {
    int[] src = new int[]{1, 9, 8, 5, 4, 2, 3, 7, 6};
    int[] tmp = new int[src.length];

    printArray(src);
    mergeSort(src, tmp, 0, src.length-1);
    printArray(src);
}

private static void mergeSort(int[] src, int[] tmp, int start, int end) {
    if(start < end) {
        int mid = (start + end) / 2;
        mergeSort(src, tmp, start, mid);
        mergeSort(src, tmp, mid+1, end);
        merge(src, tmp, start, mid, end);
    }
}

private static void merge(int[] src, int[] tmp, int start, int mid, int end) {
    // 분할1 인덱스 p : start 부터 mid 까지
    // 분할2 인덱스 q : mid+1 부터 end 까지
    // 임시보관용 인덱스 tmpIdx : start 부터 end 까지
    int p = start, tmpIdx = start;
    int q = mid + 1;

    while(p <= mid || q <= end) { // p, q 둘중 하나라도 끝나지 않은 경우 반복 

        // q 만 끝난 경우 또는 p,q 모두 안끝나고 src[p] 가 src[q] 보다 먼저인 경우
        if(q > end || (p <= mid && src[p] <= src[q])) {
            // 값을 임시보관소로 복사하며 인덱스는 1씩 증가시킨다. 
            tmp[tmpIdx++] = src[p++];
        } else {
            // 값을 임시보관소로 복사하며 인덱스는 1씩 증가시킨다. 
            tmp[tmpIdx++] = src[q++];
        }
    }

    // 임시보관소에서 결과용 메모리로 복사 
    for(int i=start; i<=end; i++) {
        src[i] = tmp[i];
    }
}


public static void printArray(int[] a) {
    for (int i=0;i<a.length;i++)
        System.out.print(a[i]+" ");
    System.out.println();
}