소규모 데이터셋의 Overhead 최소화를 통한 O(n) 최적 성능 달성

Context

일반적인 O(n log n) 알고리즘은 작은 데이터셋에서 높은 상수 시간 오버헤드를 발생시킴. 특히 이미 정렬된 데이터나 매우 작은 배열을 처리할 때 불필요한 연산 비용이 발생하는 한계 존재.

Technical Solution

• 64개 미만 요소의 배열 처리 시 Timsort 내부에서 Insertion Sort를 채택하여 오버헤드 제거
• Right-to-Left 비교 방식을 통한 데이터의 적정 위치 삽입 구조 설계
• 데이터 스트림 도달 시 즉시 정렬 가능한 Online Algorithm 특성 활용
• 정렬된 상태의 데이터에 대해 불필요한 비교를 생략하는 Near-linear 성능 최적화
• In-place 정렬 방식을 통한 Space Complexity O(1) 유지 및 메모리 효율 극대화