비교 기반 정렬 - 배열을 앞에서부터 순회하면서 정렬된 부분의 적절한 위치에 값을 삽입하는 방식
오름차순 정렬할 때:
인덱스 i에 있는 a를 정렬할 차례일 때 인덱스 0부터 i-1까지는 이미 정렬된 상태이며,
이때 배열의 정렬된 부분에서 a보다 작거나 같은 수와 a보다 큰 수 사이에 a를 삽입한다.
| 정렬된 부분 | a | ... |
| a보다 작거나 같은 수 |
a | a보다 큰 수 |
a | ... |
전체 배열을 순회하며 각 순회에서 인덱스 i 요소를 적절한 위치에 삽입하기 위해 최대 n-1번 탐색
시간 복잡도 : O(n²)