[알고리즘/이론]비교정렬의 최악의 경우

정렬에서는 최악의 경우의 수행시간이 중요하다. 그런데 각 원소를 비교하며 정렬하는 비교정렬의 경우(ex) 병합정렬, 퀵 정렬, 힙정렬 etc) 최악의 경우의 Ω(nlgn) 비교가 필요한다고 한다. 입력에 대해 순서를 결정하기 위해 필요한 비교를 트리로 나타낸 것을 결정트리라고 한다. 어떠한 입력에 대해서도 정렬된 순열을 출력하기 위해서는 입력에 대해 가능한 모든 순열을 만드는 결정트리가 존재해야 한다. 이때 결정트리의 루트와 리프 사이의 가장 긴 거리가 비교 횟수가 가장 많은 최악의 경우이며 이 값은 트리의 높이에 해당한다. n개의 입력에 대해 가능한 순열은 n!이며 이때 트리의 높이는 lg(n!) = Ω(nlg(n)) 이다. 따라서 최악의 경우는 하한은 nlg(n)이다. 즉, 비교 정렬의 경우 아무리 최적화해도 최악의 경우에 적어도 nlg(n)의 수행시간을 가진다는 것이다. 그런 측면에서 최악의 경우 O(nlg(n))을 가지는 병합정렬과 힙정렬에 대해 보다 빠른 비교 정렬은 찾기 어려울 것이다.