[Algorithm] 병합 정렬(Merge Sort)

설명

• 반으로 쪼개서 정렬 후 병합하는 분할 정복 방식의 정렬
• 정확히 반씩 나눠 정렬을 진행하기 때문에 거의 정렬된 상태에서도 시간 복잡도가 늘어나지 않음
• 메모리를 추가적으로 사용하는게 단점
• 평균적으로 퀵정렬보다 빠르진 않지만 O(N * logN)의 속도를 보장
• 시간 복잡도 : O(N * logN)
• 참고
  • https://youtu.be/ctkuGoJPmAE

예시

1. 초기 데이터

• 3 7 8 1 5 9 6

2. 반으로 분할

• step1) 3 7 8 | 1 5 9 6
• step2) 3 | 7 8 | 1 5 | 9 6
• step3) 3 | 7 | 8 | 1 | 5 | 9 | 6

3. 두 버킷의 시작점(i, j)부터 비교해 작은 값부터 앞으로 오도록 정렬

• 3(i) | 7(j) | 8 | 1 | 5 | 9 | 6 → 3 7 | 8 | 1 | 5 | 9 | 6
• 3 7 | 8(i) | 1(j) | 5 | 9 | 6 → 3 7 | 1 8 | 5 | 9 | 6
• 3 7 | 1 8 | 5(i) | 9(j) | 6 → 3 7 | 1 8 | 5 9 | 6
• 3(i) 7 | 1(j) 8 | 5 9 | 6 → 1 3 7 8 | 5 9 | 6
• 1 3 7 8 | 5(i) 9 | 6(j) → 1 3 7 8 | 5 6 9
• 1(i) 3 7 8 | 5(j) 6 9 → 1 3 5 6 7 8 9

코드

public class Solution {
    public static int[] sort(int[] data) {
        mergeSort(new int[data.length], data, 0, data.length - 1);

        return data;
    }

    private static void mergeSort(int[] temp, int[] data, int min, int max) {
        // 크기가 1보다 큰 경우
        if (min < max) {
            int middle = (min + max) / 2;
            mergeSort(temp, data, min, middle);
            mergeSort(temp, data, middle + 1, max);
            merge(temp, data, min, middle, max);
        }
    }

    private static void merge(int[] temp, int[] data, int min, int middle, int max) {
        int i = min;
        int j = middle + 1;
        int k = min;

        // 작은 값부터 배열에 삽입
        while (i <= middle && j <= max) {
            if (data[i] <= data[j]) {
                temp[k++] = data[i++];
            } else {
                temp[k++] = data[j++];
            }
        }

        // i 원소가 남아 있는 경우
        while (i <= middle) {
            temp[k++] = data[i++];
        }

        // j 원소가 남아 있는 경우
        while (j <= max) {
            temp[k++] = data[j++];
        }

        for (int t = min; t <= max; t++) {
            data[t] = temp[t];
        }
    }
}

class SolutionTest extends Specification {
    @Unroll
    def "#data -> #result"() {
        expect:
        Solution.sort(data as int[]) == result

        where:
        data                            | result
        [1, 10, 5, 8, 7, 6, 4, 3, 2, 9] | [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
        [7, 6, 5, 8, 3, 5, 9, 1]        | [1, 3, 5, 5, 6, 7, 8, 9]
    }
}