File StrandSort.h

↰ Parent directory (ADS/sort)

The strand sort, beyond the book, on a list with pointers [see File List.h]: a strand, i.e., the first item and every later one not smaller than the last taken, is pulled out of the list and merged with the result, until the list is empty.

Definition (ADS/sort/StrandSort.h)

Detailed Description

Pulling a strand and merging it cost O( n ), and there are as many strands as the decreasing runs suggest: O( n ) on a sorted list and :math:` O( n^2 ) ` on a decreasing one. It is stable, and moves cells instead of items, as the natural merge sort of which it is a variant.

The contracts [see File Contract.h]: the list ends sorted, an audit. The function is defined in StrandSort.tpp.

    1. Knuth, The Art of Computer Programming, vol. 3, 2nd ed., Addison-Wesley, 1998, section 5.2.4 (natural merging)

Donato Meoli

Dipartimento di Informatica Universita’ di Pisa

by Donato Meoli

Includes

Namespaces

Functions