삽입 정렬

배열 앞부분을 정렬된 상태로 유지하면서, 다음 원소를 그 앞부분의 알맞은 자리에 끼워 넣는 일을 반복하는 정렬이다. 카드 게임에서 손에 든 카드를 정리하는 방식과 같다. 이미 거의 정렬된 배열이면 원소마다 비교 한두 번으로 자리가 정해져 O(n)에 가깝게 끝난다.