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 absolute minimum.

@article{KV2003J,
  author = {Jyrki Katajainen and Fabio Vitale},
  title = {Navigation piles with applications to sorting, priority queues, and
    priority deques},
  journaltitle = {Nordic Journal of Computing},
  volume = {10},
  number = {3},
  year = {2003},
  pages = {238--262},
}