File Smoothsort.h

↰ Parent directory (ADS/sort)

Smoothsort of Dijkstra, beyond the book: a heapsort on a forest of Leonardo heaps, whose sizes are Leonardo numbers :math:` L_0 = L_1 = 1 , L_{k+2} = L_{k+1} + L_k + 1 `, laid side by side in the vector with the roots increasing from left to right; the forest grows by one item at a time, merging the two rightmost heaps when their orders are consecutive, and shrinks by removing the root of the rightmost heap, which is the maximum.

Definition (ADS/sort/Smoothsort.h)

Detailed Description

It sorts in place in :math:` O( n log n ) ` time like heapsort, but in O( n ) on a vector that is already sorted, the transition between the two being smooth, whence the name; it is not stable. The forest is kept as a word of bits p, the orders of its heaps relative to the order pshift of the rightmost one, as in the classical implementations.

The contracts [see File Contract.h]: the vector ends with the same items sorted, an audit. The function is defined in Smoothsort.tpp.

    1. Dijkstra, Smoothsort, an alternative for sorting in situ, Science of Computer Programming 1(3), 223-233, 1982, doi:10.1016/0167-6423(82)90016-8

Donato Meoli

Dipartimento di Informatica Universita’ di Pisa

by Donato Meoli

Includes

Namespaces

Functions