Tim Sort

Tim Sort는 다음과 같은 핵심 아이디어를 기반으로 동작합니다.

1. Run: 입력 배열을 오름차순 또는 내림차순으로 정렬된 작은 부분 배열 (run)으로 나눕니다.
2. 최소 run 크기 (minrun): run의 최소 크기를 설정하여 작은 run들을 병합하는 횟수를 줄입니다.
3. 삽입 정렬 (Insertion Sort): 작은 run들을 정렬하는 데 사용됩니다.
4. 병합 정렬 (Merge Sort): 정렬된 run들을 병합하여 전체 배열을 정렬합니다.

구현 단계

1. 최소 run 크기 결정

private static final int MIN_MERGE = 32; // 경험적으로 32가 가장 효율적

2. run 생성 및 삽입 정렬

public static void timSort(int[] arr) {
    int n = arr.length;

    for (int i = 0; i < n; i += MIN_MERGE) {
        int end = Math.min(i + MIN_MERGE, n);
        insertionSort(arr, i, end);
    }
}

private static void insertionSort(int[] arr, int start, int end) {
    for (int i = start + 1; i < end; i++) {
        int key = arr[i];
        int j = i - 1;

        while (j >= start && arr[j] > key) {
            arr[j + 1] = arr[j];
            j--;
        }
        arr[j + 1] = key;
    }
}

3. run 병합

public static void timSort(int[] arr) {
    // ... (run 생성 및 삽입 정렬 코드)

    for (int size = MIN_MERGE; size < n; size = 2 * size) {
        for (int left = 0; left < n; left += 2 * size) {
            int mid = Math.min(left + size, n);
            int right = Math.min(left + 2 * size, n);

            if (mid < right) {
                merge(arr, left, mid, right);
            }
        }
    }
}

private static void merge(int[] arr, int left, int mid, int right) {
    int[] temp = new int[right - left];
    int i = left, j = mid, k = 0;

    while (i < mid && j < right) {
        if (arr[i] <= arr[j]) {
            temp[k++] = arr[i++];
        } else {
            temp[k++] = arr[j++];
        }
    }

    while (i < mid) {
        temp[k++] = arr[i++];
    }

    while (j < right) {
        temp[k++] = arr[j++];
    }

    System.arraycopy(temp, 0, arr, left, temp.length);
}

전체 코드

public class TimSort {

    private static final int MIN_MERGE = 32;

    public static void timSort(int[] arr) {
        int n = arr.length;

        for (int i = 0; i < n; i += MIN_MERGE) {
            int end = Math.min(i + MIN_MERGE, n);
            insertionSort(arr, i, end);
        }

        for (int size = MIN_MERGE; size < n; size = 2 * size) {
            for (int left = 0; left < n; left += 2 * size) {
                int mid = Math.min(left + size, n);
                int right = Math.min(left + 2 * size, n);

                if (mid < right) {
                    merge(arr, left, mid, right);
                }
            }
        }
    }

    private static void insertionSort(int[] arr, int start, int end) {
        for (int i = start + 1; i < end; i++) {
            int key = arr[i];
            int j = i - 1;

            while (j >= start && arr[j] > key) {
                arr[j + 1] = arr[j];
                j--;
            }
            arr[j + 1] = key;
        }
    }

    private static void merge(int[] arr, int left, int mid, int right) {
        int[] temp = new int[right - left];
        int i = left, j = mid, k = 0;

        while (i < mid && j < right) {
            if (arr[i] <= arr[j]) {
                temp[k++] = arr[i++];
            } else {
                temp[k++] = arr[j++];
            }
        }

        while (i < mid) {
            temp[k++] = arr[i++];
        }

        while (j < right) {
            temp[k++] = arr[j++];
        }

        System.arraycopy(temp, 0, arr, left, temp.length);
    }
}

결론

Tim Sort는 효율적인 정렬 알고리즘이지만, 직접 구현하는 것은 다소 복잡합니다. 실제 사용 시에는 Java의 내장 Arrays.sort()를 사용하는 것이 성능 면에서 더 효율적입니다. (Java 14부터 적용)