[Java] 합병정렬 Merge Sort

합병정렬 - 배열을 두 부분으로 계속 나눈 뒤 다시 나눠진 배열을 비교해 나가면서 합치면서 정렬된다. 재귀적

시간복잡도 O(n log n)

각각의 병합 시간 O(n)

각 재귀 호출은 주어진 리스트 숫자의 절반만큼 발생

public void mergeSort(int num[], int length) {
    int center = length / 2;
    int leftNum[] = new int[center];
    int rightNum[] = new int[length - center];

    if (length == 1) return;


    //왼쪽배열
    for (int i = 0; i < center; i++) {
        leftNum[i] = num[i];
    }
    //오른쪽배열
    for (int i = 0; i < length - center; i++) {
        rightNum[i] = num[center + i];
    }
    //배열체크
    System.out.println("leftArray" + Arrays.toString(leftNum));
    System.out.println("rightArray" + Arrays.toString(rightNum));

    // 왼쪽 오른쪽 배열 나눔 재귀
    mergeSort(leftNum, leftNum.length);
    mergeSort(rightNum, leftNum.length);

    merge(leftNum, rightNum, num);

}

private void merge(int[] leftNum, int[] rightNum, int[] num) {
    int left = 0;
    int right = 0;
    int merge = 0;

    while (leftNum.length != left && rightNum.length != right) {
        if (leftNum[left] < rightNum[right]) {
            num[merge] = leftNum[left];
            merge++;
            left++;
        } else {
            num[merge] = rightNum[right];
            merge++;
            right++;
        }
    }

    while (leftNum.length != left) {
        num[merge] = leftNum[left];
        merge++;
        left++;
    }

    while (rightNum.length != right) {
        num[merge] = rightNum[right];
        merge++;
        right++;
    }

}