Journal of the Association for Computing Machinery, Vol. 43, No. 2, March 1996, pp. 331–361.

Sorting on a Parallel Pointer Machine with Applications to Set Expression Evaluation

MICHAEL T. GOODRICH

AND

S. RAO KOSARAJU

Abstract. We present optimal algorithms for sorting on parallel CREW and EREW versions of the pointer machine model. Intuitively, one can view our methods as being based on a parallel mergesort using linked lists rather than arrays (the usual parallel data structure). We also show how to exploit the “locality” of our approach to solve the set expression evaluation problem, a problem with applications to database querying and logic-programming, in O(log n) time using O(n) processors. Interestingly, this is an asymptotic improvement over what seems possible using previous techniques.

Categories and Subject Descriptors. E.1 [Data Structures]—arrays; lists; F.2.2 [Analysis of Algorithms and Problem Complexity]: Nonnumerical Algorithms and Problems— sorting and searching

General Terms. Algorithms, Theory, Verification

Additional Key words and Phrases. Cascade merging, expression evaluation, linking automaton, mergesort, parallel algorithms, pointer machine, PRAM

Copyright 1996 by ACM, Inc. Permission to make digital or hard copies of part or all of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or direct commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, to republish, to post on servers, or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from Publications Dept, ACM Inc., fax +1 (212) 869-0481, or permissions@acm.org.