Maintaining a monotonic labeling of an ordered list during the insertion of n items requires $\Omega$(n log n) individual relabelings, in the worst case, if the number of usable labels is only polynomial in n. This follows from a lower bound for a new problem, prefix bucketing.

A simple algorithm for solving a version of thepartially persistent sorted set problemis given. The algorithm requiresO(n) space andO(n log n) time to handlenoperations. Unlike Sarnak and Tarjan's algorithm, the new algorithm can make use of any of the existing balanced tree schemes that can be implemented with “path copying,” at the expense of not efficiently implementing some operations on partially persistent search trees.

The order maintenance problem is that of maintaining a list under a sequence of Insert and Delete operations, while answering Order queries (determine which of two elements comes first in the list). We give two new algorithms for this problem. The first algorithm matches the O(1) amortized time per operation of the best previously known algorithm, and is much simpler. The second algorithm permits all operations to be performed in O(1) worst-case time.

We present a new representation for linked lists. This representation allows one to efficiently insert objects into the list and to quickly determine the order of list elements. The basic data structure, called an indexed 2-3 tree, allows one to do n inserts in O(nlogn) steps and to determine order in constant time. We speed up the algorithm by dividing the data structure up into log*n layers. The improved algorithm does n insertions and comparisons in O(nlog*n) steps. The paper concludes with two applications: determining ancestor relationships in a growing tree and maintaining a tree structured environment (context tree).