원소 수 10인 배열을 삽입 정렬로 오름차순 정렬한다. 두 번째 이후의 원소를 차례로 꺼내어, 왼쪽 이웃부터 차례로 비교하며 꺼낸 값 이하인 원소가 발견되거나 맨 앞에 도달할 때까지 비교한다. 처음부터 오름차순으로 늘어서 있는 경우와 내림차순으로 늘어서 있는 경우의 비교 횟수의 조합은?

정답: C. 9회와 45회

오름차순으로 늘어서 있으면 꺼낸 값은 왼쪽 이웃과 1회 비교하는 것만으로 위치가 정해지므로, 9개의 원소에서 합계 9회입니다. 내림차순이면 i번째로 꺼내는 값은 왼쪽에 있는 i개 모두와 비교하므로 1 + 2 + … + 9 = 45회가 됩니다. 이처럼 삽입 정렬은 최선 O(n), 최악 O(n²)으로 입력에 따라 크게 달라지며, 거의 정렬된 데이터에는 매우 빠르다는 특징이 있습니다. 이 성질을 살려 간격을 둔 원소끼리 먼저 삽입 정렬을 하는 것이 셸 정렬이며, Timsort 등도 짧은 구간에 삽입 정렬을 사용합니다.