Online List Labeling with Near-Logarithmic Writes

Martin P. Seybold

In the Online List Labeling problem, a set of $n\le N$ elements from a totally ordered universe must be stored in sorted order in an array with $m=N+\lceil \epsilon N\rceil$ s…