삽입 정렬

배열이나 리스트의 원소를 하나씩 비교하면서 알맞은 위치에 삽입하여 정렬하는 방법

쉽게 생각하면 배열 앞부분부터 정렬을 시작하고 모든 배열이 정렬될 때 까지 하나씩 정렬 영역에 알맞는 위치에 삽입하는 정렬 방법이다.

선택 정렬과 마찬가지로 O(n^2)의 비효율적인 시간 복잡도를 가지게 된다.

정렬을 하는 방법인데 정렬이 안되어있을수록 성능이 떨어지게 된다. 정렬이 어느정도 잘 되어있다는 보장이 있다면 좋을 수 있지만 그렇지 않다면 다른 정렬 방법이 선호된다.