The Log-Interleave Bound: Towards the Unification of Sorting and the BST Model

We study the connections between sorting and the binary search tree model, with an aim towards showing that the fields are connected more deeply than is currently known. The main vehicle of our study is the log-interleave bound, a measure of the information-theoretic complexity of a permutation $\pi$. When viewed through the lens of adaptive sorting -- the study of lists which are nearly sorted according to some measure of disorder -- the log-interleave bound is comparable to the most powerful known measure of disorder. Many of these measures of disorder are themselves virtually identical to well-known upper bounds in the BST model, such as the working set bound or the dynamic finger bound, suggesting a connection between BSTs and sorting. We present three results about the log-interleave bound which solidify the aforementioned connections. The first is a proof that the log-interleave bound is always within a $\lg \lg n$ multiplicative factor of a known lower bound in the BST model, meaning that an online BST algorithm matching the log-interleave bound would perform within the same bounds as the state-of-the-art $\lg \lg n$-competitive BST. The second result is an offline algorithm in the BST model which uses $O(\text{LIB}(\pi))$ accesses to search for any permutation $\pi$. The technique used to design this algorithm also serves as a general way to show whether a sorting algorithm can be transformed into an offline BST algorithm. The final result is a mergesort algorithm which performs work within the log-interleave bound of a permutation $\pi$. This mergesort also happens to be highly parallel, adding to a line of work in parallel BST operations.