Comparison Sort
noun
say it: “kum-PAIR-ih-sun sort” /kəmˈpɛrɪsən sɔːrt/
A sort that learns about the items only by comparing two of them at a time.
What is a comparison sort?
A comparison sort learns about the items only by asking yes-or-no questions: is this one smaller than that one? Selection, insertion, merge sort and quicksort are all comparison sorts. n items can be in n! orders and each question at best rules out half, so no comparison sort can beat O(n log n) in the worst case.
In a sentence
- “Every comparison sort needs about n log n comparisons in the worst case, so merge sort can't be beaten by comparing.”
Level: Freelancer · More Data Structures terms at this level
Updated