삽입 정렬

자료가 정렬된 부분과 정렬되지 않은 부분으로 나누어진다. 정렬되지 않은 부분의 자료가 정렬된 부분의 자리로 삽입되는 형태의 정렬 방법

실행

정렬된 배열

삽입 정렬은 특정 실행단계에서, 어떤 원소가 정렬된 배열 내에 자리를 찾았다고 해서 그것이 최종적인 제자리라는 보장은 없다. 다음 단계가 진행되면서 다른 자료에 의해 위치가 바뀔 수 있기 때문이다. 따라서 삽입 정렬은 자료의 양이 적을 때 성능이 우수하며 자료 대부분이 이미 정렬이 되어 있는 경우 효율적이다. 삽입 정렬은 이미 정렬된 자료에 새로운 자료를 삽입해야 하는 경우가 발생하면, 정렬된 자료들이 자리를 이동해야 하므로 안정성이 낮다.

참고
https://www.edwith.org/cs50/lecture/22861?isDesc=false