Algorithms & Data Structures
the bound is a claim, and it is checkable
Theme

The thread: There is a floor

Comparison sorting cannot use fewer than log₂(n!) comparisons, and that number is computable exactly. The distance between an algorithm and the floor is a measurement rather than a feeling.
every algorithm that makes at most 4 comparisonsthe 24 orderings of 4 elementsroot16 leaves16 seated · 8 with no leafone comparison per level, two outcomes per comparison⌈log₂(4!)⌉ = 5 comparisons The floors

The floor under every comparison sort

No algorithm that sorts by comparing pairs of elements can average fewer than log₂(n!) comparisons. Not one that exists, and not one that ever will. The argument takes three sentences, it is about counting leaves in a tree, and it is one of the few results in this subject that is genuinely about every possible algorithm rather than about a particular one.

 the floorMerge sort1.02×Quicksort, first1.23×Quicksort, random1.24×Merge sort + cutoff1.29×Quicksort, median-31.32×Shellsort1.45×Heapsort1.96×Insertion sort9.69×Bubble sort19.26×Selection sort19.38×floor = log₂(256!) = 1,684 comparisonsmean of 16 runs, against a proved bound The floors

How close anything gets to the floor

The interesting question about a sorting algorithm is not its complexity class but its distance from the bound nothing can cross. Merge sort comes within 2.2% of the information-theoretic floor. Heapsort uses 96% more than it needs to. Selection sort uses nineteen times. Those three numbers say more than the classification does.

 comparisons (bar length is log-scaled)sorting, floor43,250sorting, merge sort43,976searching, floor13searching, binary13searching, linear4,096green outline: a proved floor · blue: a measured run3,327× between the two floors The floors

The floor moves when the question does

Sorting 4,096 elements needs at least 43,250 comparisons. Finding one element among the same 4,096, already sorted, needs at least 13. The difference is a factor of 3,300 and it comes entirely from how many different answers the algorithm has to be able to give. A lower bound is a property of the question, not of any algorithm.

All themes