A data structure, named a navigation pile, is described and exploited
in the implementation of a sorting
algorithm, a priority queue, and a priority deque.
When carrying out these tasks,
a linear number of bits is used in addition to the elements
manipulated, and extra space for a sublinear
number of elements is allocated if the grow
and shrink operations are to be supported.
Our viewpoint is to allow little extra space, make a low number of
element moves, and still keep the efficiency in the number of element
comparisons and machine instructions. In spite of low memory
consumption, the worst-case bounds for the number of element
comparisons, element moves, and machine instructions are close to the