A. Andersson and T. W. Lai. Comparison-efficient write-optimal searching and sorting.
In Proc. 2nd ann. International Symposium on Algorithms, pages 273--282. Springer Verlag, 1991.

(Mathematical expressions are simplified in this html-dokument. They should be readable enough to get the flavour.)

We consider the problem of updating a binary search tree in $O(\log n)$ amortized time while using as few comparisons as possible. We show that a tree of height $\lceil\log (n+1)+1/\!\sqrt{\log(n+1)}\rceil$ can be maintained in $O(\log n)$ amortized time such that the difference between the longest and shortest paths from the root to an external node is at most $2$.

We also study the problem of sorting and searching in the {\it slow write} model of computation, where we have a constant size cache of fast memory and a large amount of memory with a much slower writing time than reading time. In such a model, it is important to sort using only $\Theta(n)$ writes into the slower memory. We say that such algorithms are {\it write optimal}, and we introduce a $O(n\log n)$ time, write-optimal sorting algorithm that requires only $n\log n+O(n)$ comparisons in the worst case. No previous sorting algorithm that performs $n\log n+o(n\log n)$ comparisons in the worst case had previously been shown to be write optimal.

The above results are based on a class of trees called $k$-stratum trees, which can be viewed as a generalization of stratified search trees.

Full paper (postscript)
Full paper (pdf)