File KnuthSorts.h

↰ Parent directory (ADS/sort)

The internal sorts of Knuth that the book leaves out, beyond the book:

Definition (ADS/sort/KnuthSorts.h)

Detailed Description

  • binaryInsertionSort() (5.2.1) finds the place of each item by a binary search in the sorted prefix, :math:` sum_k lceil log_2 k rceil ` comparisons, near the least possible, but still :math:` Theta( n^2 ) ` moves; stable;

  • listInsertionSort() (Algorithm 5.2.1L) inserts each item in a list of links, so that no item moves until the end, when the list is followed to rearrange the vector: :math:` Theta( n^2 ) ` comparisons and only O( n ) moves of items; stable;

  • addressCalculationSort() (5.2.1, of Isaac and Singleton) inserts each number in one of M lists by its value, list i taking the numbers in the i-th of M equal ranges between the least and the largest, as one would file cards under the letters: O( n ) expected time on numbers spread evenly, with M about n / 4; stable;

  • radixExchangeSort() (Algorithm 5.2.2R) is the quicksort on the bits of the keys from the most significant: the part is split into the keys with the bit 0 and those with the bit 1, by exchanges as in a partition, and each half is sorted on the next bit; O( n w ) for keys of w bits, not stable;

  • tournamentSort() (5.2.3, tree selection) plays a knockout tournament on a complete binary tree of the items, the winner (the least) goes out and only the matches on its path are played again, :math:` lceil log_2 n rceil ` comparisons each: :math:` O( n log n ) ` with n extra places, the idea from which heapsort grew; stable when equal winners are broken by their places;

  • mergeInsertionSort() of Ford and Johnson (5.3.1): the items are paired and compared, the larger ones sorted recursively, and the smaller ones inserted by binary search into the chain in the order of the Jacobsthal numbers 1 , 3 , 5 , 11 , 21 , …, so that each insertion searches a prefix of :math:` 2^k - 1 ` items; it makes :math:` sum_{k=1}^n lceil log_2 ( 3 k / 4 ) rceil ` comparisons in the worst case, the fewest of any known method for most n (and the least possible for n <= 11 and n = 20 , 21), at the price of a bookkeeping that makes it slow in time; not stable.

The contracts [see File Contract.h]: each sort ends with the same items sorted, an audit. The functions are defined in KnuthSorts.tpp.

    1. Knuth, The Art of Computer Programming, vol. 3, 2nd ed., Addison-Wesley, 1998, sections 5.2.1, 5.2.2, 5.2.3 and 5.3.1

    1. Isaac, R. C. Singleton, Sorting by address calculation, Journal of the ACM 3(3), 169-174, 1956, doi:10.1145/320831.320834

  1. Hildebrandt, H. Isbitz, Radix exchange: an internal sorting method for digital computers, Journal of the ACM 6(2), 156-163, 1959, doi:10.1145/320964.320972

    1. Ford, S. M. Johnson, A tournament problem, American Mathematical Monthly 66(5), 387-389, 1959, doi:10.2307/2308750

Donato Meoli

Dipartimento di Informatica Universita’ di Pisa

by Donato Meoli

Includes

Namespaces

Functions