정렬 테마 (3)/안정적인 내부 정렬/귀속 2 - 루트 병합 정렬

public class MergeSort {
    
    /*
     *  Merge these two parts : 
     *      "fromIndex --> splitPoint"
     *      "splitPoint + 1 --> toIndex"
     */
    private static void merge(int[] array, int fromIndex, int splitPoint, int toIndex) {
        
        int[] tempArray = new int[toIndex - fromIndex + 1];
        
        int index = 0;
        
        int i = fromIndex;
        int j = splitPoint + 1;
        
        while (i <= splitPoint && j <= toIndex) {
            if (array[i] < array[j]) {
                tempArray[index ++] = array[i ++];
            } else if (array[i] == array[j]) {
                tempArray[index ++] = array[i ++];
                tempArray[index ++] = array[j ++];
            } else {
                tempArray[index ++] = array[j ++];
            }
        }
        
        while (i <= splitPoint) {
            tempArray[index ++] = array[i ++];
        }
        
        while (j <= toIndex) {
            tempArray[index ++] = array[j ++];
        }
        
        for (int k = fromIndex, m = 0; k <= toIndex; k ++) {
            array[k] = tempArray[m ++];
        }
        
    }
    
    public static void mergeSort(int[] array, int fromIndex, int toIndex) {
        
        int splitPoint = fromIndex + (toIndex - fromIndex) / 2;
        
        if (fromIndex == toIndex) {
            return;
        }
        
        mergeSort(array, fromIndex, splitPoint);
        mergeSort(array, splitPoint + 1, toIndex);
        
        merge(array, fromIndex, splitPoint, toIndex);
    }

}