삽입 정렬은 앞쪽의 정렬된 부분에 다음 원소를 알맞은 위치로 끼워 넣는 정렬이다.
원리
원소보다 큰 앞의 값들을 한 칸씩 옮기고 빈자리에 원소를 넣는다. 최악 O(n²)이지만 이미 정렬된 입력은 선형 시간에 처리하는 구현이 가능하다.
예시
2, 5까지 정렬된 상태에서 3을 처리하면 5를 오른쪽으로 옮기고 그 자리에 3을 넣는다.
주의할 점
작은 배열이나 거의 정렬된 입력에 유용하지만 큰 무작위 입력에는 이동 횟수가 많다. 같은 키를 건너뛰지 않도록 비교 조건을 정하면 안정적으로 구현할 수 있다.