삽입 정렬: 작은 정렬 구간을 다루는 안정적 알고리즘

정렬된 왼쪽 구간에 원소를 끼워 넣는 방식

삽입 정렬은 배열의 왼쪽을 이미 정렬된 구간으로 보고, 다음 원소를 그 안의 알맞은 자리에 넣어 가는 비교 기반 정렬이다. 현재 원소보다 큰 값을 오른쪽으로 한 칸씩 밀어 빈 자리를 만든 뒤, 그 자리에 현재 원소를 넣는다.

평균과 최악 시간 복잡도는 O(n^2)이다. 반면 입력이 거의 정렬되어 있다면 O(n)으로 동작할 수 있다. 추가 공간은 O(1)이며, 같은 키를 가진 원소의 상대적 순서를 보존하는 안정 정렬이다. 입력의 역전 수가 적을수록 이동도 줄어드는 적응적 특성도 있다.

입력은 길이 n의 배열 A이고, i = 1부터 n−1까지 순회한다. 각 단계에서 A[i]를 key로 잡고 왼쪽의 정렬된 구간을 훑는다. key보다 큰 원소를 오른쪽으로 옮긴 뒤 A[j+1]에 key를 넣으면, 순회가 끝났을 때 A는 비내림차순으로 정렬된다.

⤢✕

작은 구간에서 드러나는 특성

삽입 정렬은 인접한 메모리 구간을 중심으로 이동하므로 캐시 지역성이 좋다. 데이터 분포상 분기 예측 미스 비용이 낮다면 상수 계수 측면에서도 유리할 수 있다.

구현 자체도 단순하다. 추가 메모리 없이 제자리 정렬로 만들 수 있어, 코드 경량성이 필요한 임베디드·시스템 영역에서 유지보수하기 쉽다. 분할 정복 기반 정렬의 작은 구간 처리기로 연결하기도 수월하며, 전환 임계값을 두면 전체 처리량을 높이는 데 활용할 수 있다.

삽입 정렬을 선택할 수 있는 상황

크기 수십(≈8~64) 이하의 컬렉션을 즉시 정렬해야 하거나, 로그·이벤트 스트림을 시간순으로 삽입하는 경우에 사용할 수 있다. 상위-K를 유지하는 정렬된 소규모 버퍼, 데이터베이스·캐시 인덱스에서 flush 전 작은 페이지를 다시 정렬하는 작업도 대상이 된다.

하이브리드 정렬에서는 Quicksort나 Heapsort가 나눈 작은 파티션을 삽입 정렬로 처리하는 방식이 가능하다. 런(run) 기반 Timsort에서는 짧은 런을 병합하기 전 안정적인 보조 정렬기로도 쓸 수 있다.

Python 구현

전제조건은 원소끼리 상호 비교할 수 있는 컬렉션이며, 길이 n ≥ 0과 Python 3.10+를 가정한다. 외부 의존성은 없다.

# Python 3.10+
from typing import List, TypeVar, Callable, Optional

T = TypeVar("T")

def insertion_sort(a: List[T], key: Optional[Callable[[T], object]] = None) -> None:
    """
    제자리(in-place) 삽입 정렬 구현.
    - a: 정렬 대상 리스트, 비교 가능 원소로 구성
    - key: 옵션, 비교용 키 함수 (미지정 시 원소 자체 비교)
    """
    if len(a) < 2:
        return
    if key is None:
        for i in range(1, len(a)):
            k = a[i]
            j = i - 1
            while j >= 0 and a[j] > k:
                a[j + 1] = a[j]
                j -= 1
            a[j + 1] = k
    else:
        for i in range(1, len(a)):
            k = a[i]
            kv = key(k)
            j = i - 1
            # key(a[j]) 재계산 비용 존재, 소규모 입력에서 수용 가능
            while j >= 0 and key(a[j]) > kv:
                a[j + 1] = a[j]
                j -= 1
            a[j + 1] = k

if __name__ == "__main__":
    data = [5, 2, 4, 6, 1, 3]
    insertion_sort(data)
    print(data)  # [1, 2, 3, 4, 5, 6]

정렬된 prefix에서 삽입 위치를 이진 탐색으로 찾는 변형도 있다. 비교 횟수는 줄일 수 있지만, 원소를 옮기는 비용은 여전히 O(n)이다.

# Python 3.10+
import bisect

def binary_insertion_sort(a):
    """
    정렬된 prefix에 대해 bisect로 삽입 위치 탐색 후 슬라이싱 이동 수행.
    평균 비교 횟수 감소, 이동은 여전히 O(n)임.
    """
    for i in range(1, len(a)):
        key = a[i]
        # 이미 정렬된 구간 a[0:i]에서 위치 탐색
        pos = bisect.bisect_right(a, key, 0, i)
        # pos..i-1 구간을 한 칸 밀어내고 key 삽입
        a[pos+1:i+1] = a[pos:i]
        a[pos] = key

if __name__ == "__main__":
    data = [5, 2, 4, 6, 1, 3]
    binary_insertion_sort(data)
    print(data)

일반 애플리케이션에서는 sorted, list.sort처럼 Python의 Timsort를 사용하는 편이 우선이다. 삽입 정렬은 하이브리드 정렬의 작은 구간, 알고리즘 학습, 임베디드 환경처럼 특성이 맞는 곳에 한정하는 것이 좋다.

시간 복잡도와 선택 정렬·버블 정렬의 차이

하이브리드 정렬에서 소구간 크기를 864 범위로 전환하면 평균 1025% 성능이 개선된 사례가 보고되어 있다. 다만 데이터 분포와 플랫폼에 따라 달라지므로 사전 벤치마크가 필요하다.

이 알고리즘에서는 비교 횟수보다 메모리 이동 비용이 성능을 지배할 수 있다. 구조체나 레코드 크기가 큰 경우에는 포인터·인덱스를 옮기는 전략을 고려해야 한다.

알고리즘	평균 시간	최악 시간	최선 시간	공간	안정성	적응성
삽입 정렬	O(n^2)	O(n^2)	O(n)	O(1)	안정	높음
선택 정렬	O(n^2)	O(n^2)	O(n^2)	O(1)	불안정(기본)	낮음
버블 정렬	O(n^2)	O(n^2)	O(n)	O(1)	안정(기본)	중간

전환 지점과 이동 비용을 조정하는 방법

분할 정복 정렬과 결합할 때는 소구간 크기 16±를 시작점으로 두고, 마이크로벤치마크로 전환 임계값을 탐색할 수 있다. 삽입 위치 탐색에 이진 탐색을 적용하면 비교를 줄일 수 있고, 배열 앞에 센티넬을 둘 수 있는 환경이라면 경계 검사를 없앨 수 있다.

큰 객체는 참조 이동을 우선하고, 구조체는 memmove류 연산을 활용하는 방법도 고려 대상이다. 비교 순서를 정리해 브랜치 예측 비용을 줄이는 접근 역시 워크로드에 따라 검토할 수 있다.