File ListSort.h

↰ Parent directory (ADS/sequence)

The sort of a List [see File List.h] by relinking its cells, beyond the book, stable, the engineered counterpart of naturalMergeSort() [see File SequenceAlgorithms.h], which copies the items through the positions as the book does; no item is copied or moved, and the positions stay on their items.

Definition (ADS/sequence/ListSort.h)

Detailed Description

  • listSort() cuts the list into its natural runs, the maximal stretches not decreasing and those strictly decreasing, which it reverses, and merges them bottom up with an array of at most 64 runs, the run i made of about :math:` 2^i ` runs of the input, as a binary counter (the merge of std::list::sort, on the runs of the input instead of its single cells): :math:` O( n log r ) ` comparisons for r runs, n - 1 on a sorted or reversed list, and O( 1 ) extra space. The merges follow the successors only, and the predecessors are set once at the end;

  • on the numbers in their natural order (an arithmetic type and less std::less), the cells are sorted instead by an array of pairs ( key , cell ) and the LSD radix sort [see File RadixSort.h], stable, and then relinked in one pass: O( n ) time and space, two walks of the cells instead of :math:` log r ` of them, each of which misses the cache once per cell when the cells are scattered.

The contracts [see File Contract.h]: the list ends sorted by less, with the same cells (an audit). The functions are defined in ListSort.tpp.

    1. Knuth, The Art of Computer Programming, vol. 3, 2nd ed., Addison-Wesley, 1998, section 5.2.4 (Algorithm L, the merge sort of a list) and section 5.2.5 (the radix sort)

    1. McIlroy, Optimistic sorting and information theoretic complexity, Proceedings of the 4th ACM-SIAM Symposium on Discrete Algorithms (SODA), 467-474, 1993

Donato Meoli

Dipartimento di Informatica Universita’ di Pisa

by Donato Meoli

Includes

Namespaces

Functions