[정렬] Tim 정렬

TimSort (팀 정렬)

TimSort는 실제 데이터가 부분적으로 이미 정렬된(run) 경우가 많다는 점을 활용해, 작은 구간은 삽입 정렬로 빠르게 정렬하고, 그 구간들을 병합 정렬처럼 합치는 하이브리드 정렬이다. 파이썬의 list.sort(), 자바의 Arrays.sort(객체 배열) 등에서 채택된 실전형 알고리즘이기도 하다.

Point

1. Run 탐지/활용: 완전 무작위보다 부분 정렬(run)이 존재하는 실제 데이터에 강함.
2. 작은 구간 = 삽입 정렬(insertion sort): 구간 크기가 작을수록 삽입 정렬이 캐시/분기 비용 면에서 유리.
3. 큰 그림 = 병합: 정렬된 run 들을 병합 정렬 방식으로 합치면 전체 $O(nlogn)$ 을 보장.

복잡도 / 특성

항목	내용
평균/최악 시간복잡도	O(n log n)
최선 시간복잡도	O(n) (이미 정렬된 경우 run만 파악)
공간복잡도	O(n) (병합용 임시 공간)
안정성(Stable)	⭕️ 동일 값의 상대 순서 유지

로직

1. RUN 크기(RUN)만큼 배열을 쪼개 각 구간을 삽입 정렬로 정렬
2. 구간 크기를 2배씩 키워가며 인접한 두 구간을 병합
3. 전 구간이 하나의 정렬된 배열이 될 때까지 반복

코드

import java.util.Arrays;
/*
 * TimSort 구현하기
 *
 * 삽입정렬과 병합 정렬의 장점을 결합한 하이브리드 정렬 알고리즘
 * 작은 배열(ex: 길이 32이하)은 삽입정렬로 정렬한 후, 병합 정렬 방식으로 전체 배열을 병합한다.
 * */
public class Practice1 {
    // Timsort에서 사용할 RUN의 크기(작은 배열은 삽입 정렬로 정렬)
    private static final int RUN = 32;
    public static void timSort(int[] arr){
        int n = arr.length;
        for(int i = 0; i < n; i += RUN){
            insertionSort(arr, i, Math.min((i + RUN - 1), n - 1));
        }
        System.out.println("삽입정렬 수행 후의 arr : " + Arrays.toString(arr));
        /* 병합 과정에서 병합할 두 구간의 크기(size) 를 조정
         * 배열 전체를 다룰 때까지 병합할 구간의 크기를 확장
         * 한 단계마다 두 개의 정렬된 구간을 병합하여 구간 크기를 두 배로 늘림
         * 처음에는 두 개의 RUN 구간을 병합하고, 그 다음에는 두 개의 2×RUN 구간을 병합
         * */
        for(int size = RUN; size < n; size = 2 * size){
            /* 배열 전체를 순회하면서, 현재 size에 해당하는 두 개의 정렬된 구간을 찾아서 병합
             * 한 번에 두 개의 구간(각각의 크기가 size)을 병합하기 때문에
             * 병합이 끝난 후 다음 두 구간으로 건너뛰기 위해 2×size 만큼 증가
             * */
            for(int left = 0; left < n ; left += 2 * size){
                int mid = left + size -1;
                int right = Math.min(left + 2 * size - 1, n-1);
                if (mid < right) {
                    merge(arr, left, mid, right);
                }
            }
        }
    }
    /* 주어진 구간에 대해 삽입 정렬을 수행하는 메소드 */
    private static void insertionSort(int[] arr, int left, int right) {
        for(int i = left + 1; i <= right; i++){
            int key = arr[i];
            int j = i - 1;
            while(j >= left && 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 len1 = mid - left + 1;
        int len2 = right - mid;
        // 임시 배열 생성
        int[] leftArr = new int[len1];
        int[] rightArr = new int[len2];
        System.arraycopy(arr, left, leftArr, 0, len1);
        System.arraycopy(arr, mid + 1, rightArr, 0, len2);
        int i = 0, j = 0, k = left;
        // 두 임시 배열을 비교하여 정렬된 순서로 원본 배열에 복사
        while (i < len1 && j < len2) {
            if (leftArr[i] <= rightArr[j]) {
                arr[k++] = leftArr[i++];
            } else {
                arr[k++] = rightArr[j++];
            }
        }
        // 남은 요소들을 복사
        while (i < len1) {
            arr[k++] = leftArr[i++];
        }
    }
}

✔️ 주석

• RUN=32: 보통 32~64가 많이 쓰임. 데이터/환경에 맞게 조정 가능. 32 가 보편적
• 삽입 정렬: $O(RUN²)$ 이지만 RUN이 작아서 실제로 빠르다
• 병합: 두 구간 크기를 계속 2배로 키우며 전체를 하나로 합침