합병 정렬 (Merge Sort) - Java

합병 정렬이란?

• 시간복잡도 : O(NlogN)
• 표준 라이브러리에서 정렬을 구현할 때, 퀵 정렬이나 힙 정렬의 대안으로 사용하는 최적화된 정렬 알고리즘

 

합병 정렬 방법 - Divide And Conquer 

1. 주어진 리스트를 절반으로 나눈다. (Divide)

2. 해당 리스트의 길이가 1이 될 때까지 1번 과정 반복

3. 인접한 부분리스트끼리 정렬하여 합친다. (Conquer)

 

합병 정렬 구현

public class MergeSort {
    public static int[] mergeSort(int[] arr) {
        sort(arr, 0, arr.length - 1);
        return arr;
    }

    // 재귀적으로 배열을 반으로 나누어 각각 정렬
    public static void sort(int[] arr, int left, int right) {
        // base case : left와 right 가 같아지면 요소가 1개인 상태 => 정렬상태 => 리턴
        if(left == right) {
            return;
        }
        // recursive case
        // mid 값을 구하여 왼쪽과 오른쪽 부분 각각 정렬
        int mid = (left + right) / 2;
        sort(arr, left, mid);
        sort(arr, mid+1, right);

        // 정렬한 왼쪽과 오른쪽을 병합한다.
        merge(arr, left, mid, right);
    }

    public static void merge(int[] arr, int left, int mid, int right) {
        int ls = left; // 왼쪽 리스트의 시작점
        int rs = mid + 1; // 오른쪽 리스트의 시작점
        int[] tmp = new int[arr.length]; // 임시로 정렬된 값을 담아둘 배열
        int tIdx = left; // tmp 에 담아둘 요소 시작점 (left~right)

        // ls 는 최대 mid를 초과할 수 없고, rs 는 최대 right 를 초과할 수 없다.
        while(ls <= mid && rs <= right) {
            // 왼쪽 리스트와 오른쪽 리스트의 가장 왼쪽값끼리 비교한다. (정렬된 상태이므로)
            if(arr[ls] < arr[rs]) { // 왼쪽리스트의 시작점 값이 오른쪽리스트의 시작점 값보다 작다면?
                // 왼쪽 값을 tmp 에 담는다. left 부터 순차적으로 담는다.
                tmp[tIdx++] = arr[ls++]; // 담았으니 각각의 인덱스 값을 1씩 증가시킨다.
            } else { // 이 경우 오른쪽 리스트의 시작점 값을 tmp에 담는다.
                tmp[tIdx++] = arr[rs++];
            }
        }

        // while 문 통과 => 한쪽 리스트가 남아있는 상태일 수 있다.
        if(ls > mid) { // 오른쪽 리스트가 남은 상태
            while(rs <= right) {
                tmp[tIdx++] = arr[rs++];
            }
        } else { // 왼쪽 리스트가 남은 상태
            while(ls <= mid) {
                tmp[tIdx++] = arr[ls++];
            }
        }

        // tmp 의 값을 arr에 덮어씌운다.
        for(int i = left; i <= right; i++) {
            arr[i] = tmp[i];
        }
    }

    public static void main(String[] args) {
        int[] arr1 = {28, 132, 98, 30, 1, 4895, 52, 7, 123};
        int[] arr2 = {7,7,3,2,1,8,9,10,10,7};

        int[] result1 = mergeSort(arr1);
        System.out.println(Arrays.toString(result1));
        int[] result2 = mergeSort(arr2);
        System.out.println(Arrays.toString(result2));
    }
}

// 출력 결과
[1, 7, 28, 30, 52, 98, 123, 132, 4895]
[1, 2, 3, 7, 7, 7, 8, 9, 10, 10]