Efficient Parallel Cache-Oblivious Sorting Algorithms

We consider the sequential cache-oblivious and parallel cache-oblivious models of computation. First, we study Sample Partition Merge Sort (SPMS) of Cole and Ramachandran, the best-known parallel cache-oblivious deterministic sorting on these memory models. Then we present a simpler version of SPMS, which achieves a constant factor improvement in parallel time complexity over SPMS. We also present the first 1/O efficient algorithm for Bundle Sort, a stable counting sort, on these memory models. To sort an ordered list of $n$ items with $k (k < < n)$ distinct items, our sequential cache-oblivious Bundle Sort takes $O(\frac{n}{B}\log_{M}k)$ cache misses, while our parallel cache-oblivious Bundle Sort takes $O (>\log n$ log log $n$ ) parallel steps and $O(\frac{n}{B}\log_{M}k)$ cache misses. Here, $M$ is the cache memory size and $B$ is the size of each block in the cache memory.