归并排序

/**
 * 时间复杂度:lgn * n
 */
public static void mergeSort(int[] array, int startIndex, int endIndex) throws Exception {
    if (array == null) {
        throw new Exception("Array can`t be null.");
    }
    if (startIndex < endIndex) {
        int centerIndex = (startIndex + endIndex) / 2;
        mergeSort(array, startIndex, centerIndex);
        mergeSort(array, centerIndex + 1, endIndex);
        mergeArray(array, startIndex, centerIndex, endIndex);
    }
}

/**
 * 合并
 */
public static void mergeArray(int[] array, int startIndex, int centerIndex, int endIndex) {
    int[] tempArray = new int[endIndex - startIndex + 1];
    int leftIndex = startIndex;
    int rightIndex = centerIndex + 1;
    boolean leftFlag = true;
    boolean rightFlag = true;
    int temp = 0;
    while (temp <= endIndex - startIndex) {
        // 重置状态
        if (leftIndex > centerIndex) {
            leftFlag = false;
        }
        if (rightIndex > endIndex) {
            rightFlag = false;
        }
        
        if (leftFlag && rightFlag) { // 两边都有
            if (array[leftIndex] <= array[rightIndex]) {
                tempArray[temp] = array[leftIndex];
                leftIndex ++;
            } else {
                tempArray[temp] = array[rightIndex];
                rightIndex ++;
            }
        } else if (!leftFlag && !rightFlag) {   // 两边都没有
            break;
        } else if (!leftFlag && rightFlag) {    // 只有右边
            tempArray[temp] = array[rightIndex];
            rightIndex ++;
        } else {    // 只有左边
            tempArray[temp] = array[leftIndex];
            leftIndex ++;
        }
        temp ++;
    }
    
    // 复制到原数组中
    for (int copyIndex  = 0; copyIndex  < tempArray.length; copyIndex ++) {
        array[startIndex + copyIndex] = tempArray[copyIndex];
    }
}

public static void main(String[] args) throws Exception {
    int[] array = { 10, 9, 8, 7, 6, 5, 4, 3, 2, 1 };
    Utils.println(array);
    mergeSort(array, 0, array.length - 1);
    Utils.println(array);
}