6단계: 75를 올바른 위치에 삽입한다.

▲ 그림 2-10

정렬된 배열에 삽입할 때는 항상 실제 삽입 전에 검색을 먼저 수행해서 삽입할 올바른 위치를 정해야 함을 알 수 있다. 이게 바로 전형적인 배열과 정렬된 배열의 성능 차이 중 하나다.

위 예제에서는 최초에 원소가 4개였고, 삽입에 6단계가 걸렸다. N에 대해 정렬된 배열에 원소가 N개이면 삽입에 총 N + 2단계가 걸린다고 말할 수 있다.

흥미롭게도 삽입에 필요한 단계 수는 새 값이 정렬된 배열 어디에 놓이게 되든 비슷하다. 값이 정렬된 배열 앞 부분에 놓이면 비교가 줄어들고 이동이 늘어난다. 값이 뒷 부분에 놓이면 비교가 늘어나고 이동이 줄어든다. 새 값이 배열 맨 끝에 놓이면 이동하지 않아도 되니 단계 수가 가장 적다. 이때는 새 값을 기존 N값과 모두 비교하는 데 N단계가 걸리고 삽입 자체에 1단계가 걸리니 총 N+1단계다.

삽입에 있어 정렬된 배열이 전형적인 배열보다 덜 효율적이지만, 정렬된 배열의 강력함은 검색 연산에서 드러난다.