앞부분의 순서를 유지하기
왼쪽 일부가 정렬되어 있다고 보고 바로 다음 값을 그 안에 넣는다. 예를 들어 2와 7이 순서대로 놓인 뒤 5가 나오면 7을 옮기고 2와 7 사이에 5를 둔다. 처리한 앞부분이 계속 정렬되어 있다는 점이 핵심이다.
이동이 많아지는 입력
작은 값이 뒤에 몰려 있으면 앞의 여러 원소를 밀어야 한다. 이런 이동이 반복되는 배열 구현에서는 최악의 연산량이 원소 수의 제곱에 비례한다. 이미 정렬된 경우에는 각 원소의 위치를 짧게 확인하고 넘어갈 수 있다.
같은 키의 순서
같은 키를 가진 기존 원소를 넘어서지 않게 삽입하면 원래 순서를 유지하는 안정 정렬을 만들 수 있다. 어떤 비교 조건과 삽입 위치를 사용하는지가 중요하다. 알고리즘 이름만으로 모든 변형의 안정성을 단정해서는 안 된다.
탐색과 이동을 나누어 보기
삽입 위치를 찾는 비교와 공간을 만들기 위한 이동은 다른 비용이다. 위치를 이진 탐색으로 찾더라도 배열의 원소를 밀어야 하는 비용은 남는다. 비교 횟수를 줄이는 것과 전체 시간 복잡도를 바꾸는 것은 같은 주장이 아니다.