[Sort] 병합 정렬 (Merge Sort)

소개

• 많은 양의 데이터가 한 개가 될 때까지 반으로 분해하고 또 분해한다.
• 그리고 다시 그 데이터를 정렬하고 병합하는 알고리즘을 병합정렬이라 한다.
• 시간복잡도는 O(nlogn)을 가진다.

 

동작원리

• 배열을 반으로 계속 나눈다.
• 왼쪽배열이 오른쪽배열보다 작아질 때 병합을 시켜준다.
• 병합할 때 정렬을 하면서 병합한다.

 

구현 코드

public void mergeSort(int[] arr, int left, int right) {
    if (left < right) {
        int middle = (left + right) / 2;
        mergeSort(arr, left, middle);
        mergeSort(arr, middle + 1, right);
        merge(arr, left, middle, right);
    }
}

private void merge(int[] arr, int left, int middle, int right) {
    int[] temp = new int[arr.length];

    int part1 = left;
    int part2 = middle + 1;
    int index = left;

    while (part1 <= middle && part2 <= right) {
        if (arr[part1] <= arr[part2]) {
            temp[index++] = arr[part1++];
        } else {
            temp[index++] = arr[part2++];
        }
    }

    while (part1 <= middle) {
        temp[index++] = arr[part1++];
    }

    while (part2 <= right) {
        temp[index++] = arr[part2++];
    }

    for (int i = 0; i <= right - left; i++) {
        arr[i + left] = temp[i + left];
    }
}