정렬 알고리즘에는 여러가지 타입이 존재한다.정렬에는 요소들이 순차적으로 증가하게끔 만드는 오퍼레이션만 사용되며, 이는 요소의 쌍을 비교하면서 이루어진다. Exchange Sorting - Bubble Sort, Quick SortInsertion Sort Selection Sorting - Selection Sort, Heap SortMerge SortDistribution Sort - Bucket Sort, Radix Sort 정렬의 하한(lower bound)하한은 주어진 입력을 정렬하기 위해 필요한 최소 계산 작업을 의미한다. 비교 기반 정렬 알고리즘의 경우, 이 최소 비교 횟수는 보통 $\Omega(n\lg n)$이다. 여기서 어떤 비교 기반 정렬이 수행하는 비교 과정을 추상화한 것을 결정 트리 ..
