알고리즘 삽입 정렬의 주요 아이디어는, 원소를 맞는 위치로 옮기고 나머지 원소들을 밀어내는 것이다. 먼저 첫번째 원소는 정렬된 것으로 생각하며, 두번째 원소부터 연산을 시작하게 된다. 각 패스마다 n번째 원소를 기준으로 잡는다. 기준이 된 원소는 데이터를 임시로 저장해놓는다. n-1번째 원소부터 역으로 첫번째 원소까지 검사를 시작한다. 만약 검사대상이 현재 기준이 되는 값보다 큰 경우 검사대상을 한칸 뒤로 보낸다. 여기서 뒤로 보낸다는 의미는, Index를 하나 키운다는 것으로, 다른 값들을 차례차례 덮어씌운다. 예를들어 다음과 같은 원소들이 있다고 가정하자. 3, 7, 2, 6, 9, 1 첫번째 패스에서는 7을 기준으로 잡는다. 7은 임시 저장소에 저장이 되므로, 다른 값으로 덮어씌워도 상관이 없다. ..