병합 정렬(merge sort)

• 배열을 앞부분과 뒷부분으로 나누어 각각 정렬한 다음 병합하는 작업을 반복하여 정렬을 수행하는 알고리즘
• 정렬을 마친 배열의 병합을 응용하여 분할 정복법에 따라 정렬하는 알고리즘
• 먼저 배열을 앞부분과 뒷부분으로 나눈다.
• 이때 앞뒤의 각 배열을 정렬할 때는 다시 병합 정렬을 적용한다.
• 나눈 두 배열을 각각 정렬하고 병합하면 배열 모두를 정렬할 수 있다.
• 배열의 요소 개수가 2개 이상인 경우에 배열의 앞부분과 뒷부분을 각각 병합 정렬로 정렬하고 병합한다.
• java.util.Arrays 패키지에서 배열을 정렬하는 클래스 메서드인 sort를 제공한다.
  • 기본 자료형의 배열을 정렬하는 sort 메서드는 퀵 정렬 알고리즘을 개선한 것으로 안정적이진 않다.
  • 클래스 객체 배열을 정렬하는 sort 메서드는 병합 정렬을 개선한 것으로 안정적인 결과가 보장된다.

//병합 정렬
 
static int[] buff;    // 병합한 결과를 일시적으로 저장할 작업용 배열
 
// a[left] ~ a[right]를 재귀적으로 병합 정렬 
static void __mergeSort(int[] a, int left, int right) {
    if (left < right) {
        int i;
        int center = (left + right) / 2;
        int p = 0;
        int j = 0;
        int k = left;
 
        __mergeSort(a, left, center);            // 배열의 앞부분을 병합 정렬합니다.
        __mergeSort(a, center + 1, right);       // 배열의 뒷부분을 병합 정렬합니다.
 
        //병합 수행
        for (i = left; i <= center; i++)        //a 배열의 앞부분을 작업용 배열에 복사
            buff[p++] = a[i];
 
        while (i <= right && j < p)             //a 배열의 뒷부분과 작업용 배열에 복사한 a 배열의 앞부분을 병합한 과를 배열 a에 저장
            a[k++] = (buff[j] <= a[i]) ? buff[j++] : a[i++];
 
        while (j < p)                           //작업용 배열에 남은 요소를 배열 a에 복사
            a[k++] = buff[j++];
    }
}
 
// 병합 정렬
static void mergeSort(int[] a, int n) {
    buff = new int[n];                // 작업용 배열을 생성합니다.
 
    __mergeSort(a, 0, n - 1);        // 배열 전체를 병합 정렬합니다.
 
    buff = null;                    // 작업용 배열을 해제합니다.
}