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

String comparison — where it appears

Deciding the order of two strings, which costs the length of their common prefix plus one rather than a constant. How long that prefix is depends on how many keys are in play, so the cost of a comparison grows slowly with the number of things being sorted.

Named by 2 essays across 2 fields — each of them below, with the objects they name alongside it.

048162432characters every key sharesoperations072,581145,162Character comparisonsRadix sort, characters readElement comparisonsone unit = one character comparisonelement comparisons constant at 3,955

The comparison that is not one comparison

Sorting 512 keys costs 3,955 comparisons whatever the keys are, and between 7,849 and 134,409 character examinations depending only on how much those keys have in common. The first number is the one every bound so far is stated in. The second is the one the machine pays, it grows without limit, and nothing here has ever counted it.

text · Symbol 4 bytes32 bytes128 bytes512 bytesrecord:QuicksortMerge sortShellsortHeapsortInsertion sortSelection sortBubble sortQuicksortShellsortMerge sortHeapsortSelection sortInsertion sortBubble sortQuicksortShellsortMerge sortSelection sortHeapsortInsertion sortBubble sortSelection sortQuicksortShellsortMerge sortHeapsortInsertion sortBubble sort1234567n = 512, random input, key 8 bytesa read or a write moves the record; a comparison touches the key

The exchange rate nobody wrote down

Three earlier essays have said in passing that the ranking would change if the elements were large records. None of them computed it. Computed, selection sort goes from second-worst of seven at four bytes a record to best of seven at five hundred and twelve — and the crossover against each rival is a division that takes one line.

counting · Count

Named alongside it

The objects these essays reach for when they reach for this one.

Cost modelUnit of costCharacter comparisonComparison countComparison sortCrossoverData movementDistinguishing prefixMeasured countMerge sortOperation countRadix sort

All concepts