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
- comparison sort lower bound — The proven fact that any sort that only compares pairs must make at least about n log n comparisons in the worst case.
- insertion sort — A simple sort that takes items one at a time and shifts each left into its correct place among those already sorted.
- merge sort — A divide-and-conquer sort that splits the list in half, sorts each half recursively and then merges the two sorted halves.
- quicksort — A divide-and-conquer sort that picks a pivot, partitions the items into those smaller and larger than it, and sorts each part recursively.
- counting sort — A non-comparison sort for small non-negative integers that counts how many times each value occurs and then writes the values back out in order.
Taught in
- Big O, Big Omega And Big Theta — Algorithms & Data Structures for Working Engineers
- Collisions In Practice And Hash Flooding — Algorithms & Data Structures for Working Engineers
- Comparison Sorts: Insertion, Merge And Quicksort — Algorithms & Data Structures for Working Engineers
- Counting And Radix Sort: Beating N Log N — Algorithms & Data Structures for Working Engineers
- Binary Search Trees: Search, Insert And Delete — Algorithms & Data Structures for Working Engineers
- Divide And Conquer And The Recurrence — Algorithms & Data Structures for Working Engineers