  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 cache model. Our algorithms are cache oblivious
and generalize the randomized divide and conquer strategy given by Reischuk and
Reif and Sen. Although the approach yielded optimal speed-up in the PRAM model,
we require additional techniques to optimize cache-misses in an oblivious
setting. Under a mild assumption on input and number of processors our
algorithm will have optimal time and cache misses with high probability.
Although similar results have been obtained recently for sorting, we feel that
our approach is simpler and general and we apply it to obtain an optimal
parallel algorithm for 3D convex hulls with similar bounds. We also present a
simple randomized processor allocation technique without the explicit knowledge
of the number of processors that is likely to find additional applications in
resource oblivious environments.

Data Structures and Algorithms;Computational Geometry;Distributed, Parallel, and Cluster Computing