정의

삽입정렬은 카드 게임을 할 때 손에 든 카드를 정리하는 것처럼, 각 원소를 이미 정렬된 부분의 올바른 위치에 하나씩 꽂아 넣는 정렬 방법입니다.

핵심 특성

• ✓앞에서부터 정렬된 부분을 점점 확장 - 왼쪽은 항상 정렬됨
• ✓거의 정렬된 데이터에서 매우 빠름 - 최선의 경우 O(n)
• ✓안정 정렬 - 같은 값의 순서가 유지됨
• ✓작은 데이터에 효율적 - 간단하고 추가 메모리 불필요

시간 복잡도