삽입정렬: 정렬된 구간에 원소를 삽입하는 방식

정렬된 접두 구간을 넓혀 가는 방식

삽입정렬은 배열을 왼쪽의 정렬 완료 구간 S와 오른쪽의 미정렬 구간 U로 나눈다. U에서 원소 하나를 꺼내 S 안의 맞는 자리에 넣는 과정을 반복한다.

반복이 끝날 때마다 인덱스 [0..i] 구간은 오름차순으로 정렬되어 있다는 불변식이 유지된다. 최악과 평균 시간복잡도는 O(n^2)이고, 입력이 이미 정렬되어 있으면 최선 시간복잡도는 O(n)이다. 추가 메모리는 O(1)만 사용하는 제자리 정렬이며, 동일 키의 상대적 순서를 보존하는 안정 정렬이기도 하다.

이동 기반 삽입이 만드는 특성

삽입할 위치를 만들 때 원소를 교환하는 대신, 기존 원소를 오른쪽으로 이동시킨다. 그래서 별도의 저장 공간이 필요하지 않고 안정성도 유지된다.

역전 수가 적은 거의 정렬된 배열에서는 이동 횟수도 줄어든다. 이 경우 O(n)에 가까운 성능을 기대할 수 있으며, 인접한 요소를 주로 접근하므로 캐시 지역성도 좋다.

구현에서는 j > 0 경계를 먼저 검사해야 한다. 빈 배열과 원소가 하나뿐인 배열은 별도 처리 없이 종료할 수 있어야 한다. 이진 탐색으로 삽입 위치를 찾으면 비교 횟수는 O(log n)으로 줄일 수 있지만, 원소 이동 비용은 O(n)으로 남는다.

키를 꺼내고 빈 자리에 넣는 흐름

입력은 정렬할 배열 A와 크기 n이다. i=1..n-1을 순회하며 A[i]를 tmp에 저장하고, tmp보다 큰 왼쪽 원소를 한 칸씩 오른쪽으로 민다. 비어 있는 A[j]에 tmp를 넣으면 해당 반복이 끝난다.

A=null이거나 n<=1이면 즉시 종료하며, 내부 비교에서는 인덱스 하한 j>0을 확인해야 한다.

⤢✕

C99 구현에서 경계 검사를 먼저 둔다

다음 구현은 0-기반 인덱스를 사용해 오름차순으로 정렬한다. while 조건에서는 j>0을 먼저 확인해야 안전하다.

#include <stddef.h>

void insertion_sort(int *a, size_t n) {
    if (!a || n <= 1) return;
    for (size_t i = 1; i < n; ++i) {
        int tmp = a[i];
        size_t j = i;
        // 경계(j>0) → 비교 순서 유지
        while (j > 0 && a[j - 1] > tmp) {
            a[j] = a[j - 1];
            --j;
        }
        a[j] = tmp;
    }
}

질문에 제시된 data[j-1] > tmp && j >= 1 조건은 j==0일 때 data[-1]에 접근할 위험이 있다. j>0 && data[j-1] > tmp 순서가 필요하다.

작은 구간과 부분 정렬 데이터에서의 선택

퀵소트나 머지소트가 나눈 소구간이 n<=16~32일 때 삽입정렬로 전환하면 분기와 오버헤드를 줄일 수 있다. 실시간으로 적은 수의 신규 레코드를 기존의 소량 정렬 목록에 추가하는 경우에도 맞는다. 예를 들어 순소팅된 캐시 리스트에 항목을 넣는 상황이 그렇다.

타임스탬프 오차가 작은 이벤트 로그처럼 이미 대부분 정렬된 시계열 데이터를 후처리할 때도 정렬 비용을 줄이는 선택지가 된다.

다른 단순 정렬과 비교

항목	삽입정렬	선택정렬	버블정렬
평균 시간복잡도	O(n^2)	O(n^2)	O(n^2)
최선 시간복잡도	O(n)	O(n^2)	O(n)
공간복잡도	O(1)	O(1)	O(1)
안정성	안정	비안정	안정
캐시 친화성	높음	낮음	낮음
부분 정렬 적응성	높음	낮음	보통
구현 난이도	낮음	낮음	낮음

n≤32 구간에서는 O(n^2) 알고리즘이어도 비교적 낮은 상수 계수로 경쟁 알고리즘보다 빠른 경향이 있다. 추가 메모리는 0이고, 연속적인 데이터 이동은 캐시 미스 감소에 도움이 된다. 구현과 검증, 디버깅이 단순하며 안정 정렬 특성은 동일 키를 병합하는 후속 처리의 품질에도 영향을 준다.