Insertion Sort

insertion sort, 삽입 정렬

정의

Insertion Sort (삽입 정렬) 는 한 번에 한 원소씩 이미 정렬된 부분에 올바른 위치를 찾아 삽입 하는 정렬. 카드 정리하듯이 한 장씩 적절한 자리에 끼워넣는 동작.

O(n²) 알고리즘 중 실측 가장 빠르다. 작은 입력 (n ≤ 16) 이나 거의 정렬된 입력에서 Quick Sort 같은 O(n log n) 알고리즘보다도 빠를 수 있다. 그래서 Timsort, Introsort, Pdqsort 가 부분 정렬에 모두 Insertion Sort 를 사용한다.

전체 비교는 정렬 알고리즘 참고.

시각화

알고리즘

insertionSort(arr):
  for i = 1 to n-1:
    key = arr[i]
    j = i - 1
    while j >= 0 and arr[j] > key:
      arr[j + 1] = arr[j]  // 한 칸씩 오른쪽으로 밀기
      j--
    arr[j + 1] = key       // 빈 자리에 삽입

핵심 동작

배열 앞부분이 이미 정렬된 영역, 나머지가 미처리 영역. 미처리에서 하나씩 꺼내 정렬된 영역의 올바른 위치에 삽입.

[ 정렬됨 | 미처리 ]
[ 5    | 2, 8, 1, 4 ]   초기

[ 2, 5 | 8, 1, 4 ]      2 를 5 앞에 삽입
[ 2, 5, 8 | 1, 4 ]      8 은 이미 5 보다 큼, 그 자리에
[ 1, 2, 5, 8 | 4 ]      1 을 맨 앞으로
[ 1, 2, 4, 5, 8 | ]     4 를 5 앞에 삽입

매 단계에서 정렬된 영역이 정확히 정렬 상태를 유지.

복잡도

항목	값
시간 (최선)	O(n) (이미 정렬됨)
시간 (평균)	O(n²)
시간 (최악)	O(n²) (역순 입력)
공간	O(1)
안정성	✓ Stable
In-place	✓
Online	✓ (한 번에 한 원소씩 처리 가능)

왜 O(n²) 중 가장 빠른가

1. 상수항 작음: inner loop 가 단순한 비교 + 이동 한 번
2. 캐시 친화: 인접 메모리 접근만
3. 거의 정렬된 입력에 O(n) 에 가깝게 동작
4. 분기 예측 친화적: 조건이 단순

정렬된 부분의 활용

Insertion Sort 의 최대 장점은 입력의 부분적 정렬을 직접 활용 한다는 것.

const nearSorted = [1, 2, 3, 5, 4, 6, 7, 8, 9];
// 5, 4 만 어긋남
// insertion sort: 4 를 한 칸 이동 → 1 swap, 끝
// O(n) 실측

이 성질이 Timsort (Python sorted, Java Arrays.sort) 의 기반:

1. 입력에서 자연스러운 run (정렬된 부분) 식별
2. 짧은 run 은 Insertion Sort 로 길이 맞춤
3. run 들을 Merge Sort 로 합침

하이브리드 알고리즘에서의 역할

알고리즘	Insertion Sort 사용 시점
Timsort	짧은 run 정렬 (n < 64)
Introsort (C++ std::sort)	작은 부분 (n ≤ 16)
Pdqsort (Rust)	작은 부분
Dual-Pivot QS (Java)	작은 부분

Binary Insertion Sort

삽입 위치를 이진 탐색 으로 찾음. 비교 횟수는 O(n log n) 이지만 이동 횟수는 여전히 O(n²). 비교 비용이 비싼 경우 (예: 긴 문자열) 에 유리.

일반: O(n) 비교 × O(n) = O(n²)
이진: O(log n) 비교 × O(n) = O(n log n) 비교
       O(n) 이동 × O(n) = O(n²) 이동

총 비용은 여전히 O(n²) 지만 비교 횟수가 줄어든다.

Bubble / Selection 과의 비교

항목	Insertion	Bubble	Selection
실측 속도	가장 빠름	가장 느림	중간
안정성	✓	✓	✗
거의 정렬된 입력	O(n)	O(n) (early exit)	O(n²)
비교 횟수	O(n²)	O(n²)	O(n²)
교환 횟수	O(n²)	O(n²)	O(n)

실무 활용 (의외로 자주)

Insertion Sort 자체로는 작은 입력에 한정되지만, 하이브리드 알고리즘의 부속품 으로 거의 모든 표준 라이브러리에 들어가 있다.

• Python sorted(), list.sort() → Timsort 내부
• Java Arrays.sort() (객체) → Timsort 내부
• C++ std::sort → Introsort 내부 (n ≤ 16 에서)
• Rust slice::sort_unstable → Pdqsort 내부

n=8 같은 작은 배열을 정렬할 일이 있으면 Insertion Sort 가 올바른 선택.

참고

• 정렬 알고리즘
• Bubble Sort
• Selection Sort
• Merge Sort
• Quick Sort
• Knuth, TAOCP Vol. 3 §5.2.1