SORTING ON A PARALLEL POINTER MACHINE WITH APPLICATIONS TO SET EXPRESSION EVALUATION

We present optimal algorithms for sorting on parallel CREW and EREW ve rsions of the pointer machine model. Intuitively, one can view our met hods as being based on a parallel mergesort using linked lists rather than arrays (the usual parallel data structure). We also show how to e xploit the ''locality'' of our approach to solve the set expression ev aluation problem, a problem with applications to database querying and logic-programming, in O(log n) time using O(n) processors. Interestin gly, this is an asymptotic improvement over what seems possible using previous techniques.