Proximity Mergesort: optimal in-place sorting in the cache-oblivious model

Abstract

An algorithm performs its operations in-place if it uses O(1) extra locations of main memory besides those containing the input entries. An algorithm is cache-oblivious if it is not conscious of any parameter of the memory hierarchy (M, the size of cache memory, and B, the size of the minimal contiguous block of information that can be transferred between the cache and the main memory). Hence, it cannot directly exploit these parameters to reach the optimality. In the cache-oblivious model the complexity is measured with two criteria: the work complexity, which is the standard complexity in the RAM model, and the cache complexity, which is the total number of block transfers (cache misses) incurred during the computation.The contribution of this paper is twofold. We present the first sorting algorithm that is optimal in both work and cache complexity in the cache-oblivious model and that operates in-place. Furthermore, we introduce a new approach to the sorting problem in the cache-oblivious model.