구현 방식

삽입 정렬의 틀은 '어떠한 값'이 '어느 곳'에 삽입되어야 하는지를 판단하여 삽입하는 것이다. 이때 '어떠한 값'은 배열의 2번째 값부터 마지막 값까지 순차적으로 지정될 것이고, '어느 곳'은 0번째 인덱스부터 '어떠한 값'의 인덱스 이전까지의 범위 내를 의미한다.

어떠한 값이 있는 인덱스의 이전 인덱스로 부터 0번째 인덱스까지 탐색하여 어떠한 값이 들어갈 위치를 찾는다.

시간 복잡도

만약 이미 정렬되어있는 상태라면 비교를 한 번만 진행해도 되기 때문에 $O(N)$만큼의 시간이 소요된다. 그러나 역으로 정렬되어있는 경우 모든 원소와 비교해야하기 때문에 $O(N^2)$만큼의 시간이 소요된다.

공간 복잡도

삽입 정렬은 하나의 배열 내부에서 이루어진다. 따라서 배열의 크기인 $O(N)$이다.