Sorting on a parallel pointer machine with applications to set expression evaluation

Optimal algorithms for sorting on parallel CREW (concurrent read, exclusive write) and EREW (exclusive read, exclusive write) versions of the pointer machine model are presented. Intuitively, these methods can be viewed as being based on the use of linked lists rather than arrays (the usual parallel data structure). It is shown how to exploit the `locality´ of the approach to solve a problem with applications to database querying and logic programming (set-expression evaluation) in O(log n) time using O(n) processors