• 삽입 정렬이란 정렬을 진행할 원소의 index보다 낮은 곳에 있는 원소들을 탐색하며 알맞은 위치에 삽입해주는 정렬 알고리즘이다.

• 동작 방식은 두번째 Index 부터 시작한다. (0번째 인덱스는 이전인덱스가 존재하지 않아 비교할 원소가 없기 때문이다.

모두 정렬 되어 있는 경우에는 모든 원소가 한 번씩만 비교되므로

최적의 경우 시간복잡도는 $O(n)$을 가진다.

하지만 평균 및 최악의 경우는 모두 비교해야 하므로 $O(n^2)$ 이다.

공간복잡도의 경우 하나의 배열만 사용하므로 $O(n)$ 의 공간 복잡도를 가진다.