우리는 하루에도 여러 번 포털 사이트 혹은 검색 엔진을 이용하여 정보를 찾곤 합니다. 인터넷에 널려 있는 수억, 수조개의 정보 중, 주어진 검색어에 가장 가까운 (혹은 가장 적합한) 정보를 담고 있는 웹페이지들은 1초도 안 되는 시간 동안 사용자의 모니터에 뜨기 시작합니다. 구글 검색을 할 경우, 관련된 정보들은 1페이지부터 시작하여 N번째 페이지까지 나열됩니다. 물론 대부분의 사용자들은 1페이지에 있는 웹문서들을 살펴 보는 정도로 검색을 마치곤 합니다. 2페이지까지 넘어가는 경우도 거의 없습니다. 검색 엔진이 인터넷에 널려 있는 정보들을 찾아서 사용자에게 보여줄 때, 2페이지로 넘어가기도 어려워하는 (귀찮아하는) 사용자들의 만족도를 높이기 위해서는 결국 1페이지 안에 사용자가 찾는 최적의 정보를 나열하는 전략이 매우 중요할 것입니다. 이는 검색 대상 정보들 중, 검색어에 가장 적합한 문서들을 '순서대로' 나열하는 것이 매우 중요함을 의미합니다. 그리고 그 순서를 찾는 시간이 많이 걸리면 안 될 것입니다. 왜냐하면 대부분의 사용자들은 단 1초의 기다림도 지루해하기 때문입니다.

문제는 수많은 정보를 과연 어떻게 정렬할 것이냐는 것입니다. 예를 들어 5, 1, 3, 4, 2 로 이루어진 수열을 생각해 봅시다. 여기서 각 숫자는 검색어와 연관된 정도를 나타내는 랭킹을 의미합니다. 검색 엔진은 이 수열을 사용자를 위해 내림차순으로 정리하려 합니다. 즉, 1, 2, 3, 4, 5로 정돈하고 싶은 것이죠. 이 과정에서 필요한 전략은 바로 정렬 알고리즘 (sorting algorithm)입니다. 정렬 알고리즘은 현대 컴퓨터 과학의 가장 중요한 분야이쟈, 계속 연구되면서 실생활에 바로 응용되는 분야이기도 합니다. 정보량이 폭증하는 현대 사회에서는 조금이라도 시간을 절약하고 에너지를 (즉, 정렬 계산에 필요한 전기 에너지) 절약할 수 있는 정렬 알고리즘의 가치는 더욱 높아질 수 밖에 없습니다.

정렬 알고리즘의 효율을 나타낼 때 쓰는 지표는 계산에 걸리는 시간복잡도입니다. 보...