정렬된 배열(ordered array)은 1장에서 설명한 “전형적인” 배열과 거의 같다. 유일한 차이는 정렬된 배열이라는 이름에서 추측할 수 있듯이 값이 항상 순서대로 있어야 한다는 점이다. 즉, 값을 추가할 때마다 적절한 셀에 넣어 배열의 값을 정렬된 상태로 유지한다.

배열 [3, 17, 80, 202]를 예로 들어 보자.

▲ 그림 2-1

75를 삽입해 보자. 전형적인 배열이면 다음처럼 끝에 75를 삽입할 것이다.

▲ 그림 2-2

1장에서 설명했듯이 컴퓨터는 단 한 단계로 삽입을 처리할 수 있다.

반면 정렬된 배열에서는 값을 오름차순으로 유지하려면 적절한 위치에 75를 삽입해야 한다.

▲ 그림 2-3