Efficient cache oblivious algorithms for randomized divide-and-conquer on the multicore model

Neeraj Sharma, Sandeep Sen

In this paper we present randomized algorithms for sorting and convex hull that achieves optimal performance (for speed-up and cache misses) on the multicore model with private cac…