Nearly Sorted 데이터에서 O(n) 성능을 구현하는 Insertion Sort 최적화

Context

일반적인 정렬 알고리즘은 최악의 경우 높은 시간 복잡도를 가지며, 이미 정렬된 상태의 데이터가 유입되는 환경에서 불필요한 연산을 반복하는 한계 존재. 특히 QuickSort와 같은 분할 정복 알고리즘은 데이터 상태와 무관하게 재귀적 분할 과정을 거치므로 오버헤드 발생 가능성 높음.

Technical Solution

• Mobile Boundary 개념을 통한 배열의 Sorted/Unsorted 영역 분리 설계
• In-Place Sorting 방식을 채택하여 추가적인 메모리 할당 없는 O(1) 공간 복잡도 달성
• Key 값 추출 후 Sorted 영역을 역방향으로 탐색하며 적절한 위치에 삽입하는 Shift 로직 구현
• Nearly Sorted 데이터 유입 시 불필요한 데이터 이동을 최소화하여 연산 횟수 단축
• Online Algorithm 특성을 활용하여 데이터 스트림 유입 즉시 정렬 상태를 유지하는 실시간 처리 구조 설계
• 동일 값의 상대적 순서를 보존하는 Stable 정렬 특성을 통해 데이터 무결성 유지