comparison sort

A sorting algorithm that learns about the order only by asking "is a smaller than b?" about pairs of items.

In more detail

Insertion sort, merge sort, quicksort and heap sort are comparison sorts, and they work on any items that can be compared. No comparison sort can beat O(n log n) comparisons in the worst case. Counting and radix sort escape that limit by reading keys directly instead of comparing them.

Related terms

Taught in

References