앞쪽은 이미 정렬되어 있다고 보고, 새 원소를 그 안의 올바른 자리에 끼워 넣는 정렬. 손에 든 카드를 정리하는 방식과 같다. 0번째는 혼자라 이미 정렬된 상태이므로 1번째부터 시작한다.
거의 정렬된 입력에서의 강점
평균과 최악은 O(n²)인데 최선이 O(n)이다. 이미 정렬된 배열이면 각 원소가 바로 앞 값보다 크다는 것만 확인하고 끝나기 때문이다. 거의 정렬된 데이터에서 아주 빠르다는 게 이 정렬의 진짜 강점이고, 팀소트 같은 실무 정렬이 작은 구간에서 삽입 정렬을 쓰는 이유다.
제자리와 안정성
공간복잡도는 O(1)이다. 다만 새 배열을 만들어 거기 넣는 식으로 구현하면 O(n)이 되니, 원본 안에서 밀어내는 방식이어야 제자리 정렬이다. 비교 대상이 새 원소보다 클 때만 뒤로 밀기 때문에 같은 값을 만나면 그 뒤에 자리를 잡고, 그래서 안정 정렬이다.
비교를 멈추는 지점과 밀어내기
최적화도 둘 있다. 앞쪽은 이미 정렬되어 있으니 끝까지 비교할 필요가 없다. [1, 2, 3, 5]에 4를 넣을 때 3이 4보다 작다는 것만 확인하면 그 앞은 전부 4보다 작으니, while 문 조건에 비교를 넣어 그 시점에 멈추면 된다. 교환도 필요 없다. 앞의 값이 새 원소보다 크면 뒤로 한 칸 밀고, 밀 수 없는 지점을 만나면 그 자리에 새 원소를 꽂는다. swap은 값을 세 번 옮기지만 이 방식은 한 번씩만 옮긴다.
이동 횟수 세기
동작을 알면 정렬하지 않고 답이 나오는 문제도 있다. “이 배열을 삽입 정렬하면 원소가 몇 번 이동하는가”를 물으면, 실제로 돌릴 것 없이 각 원소 앞에 자기보다 큰 원소가 몇 개인지 세면 그게 이동 횟수다.