Abstract
In this paper, two cost-optimal parallel algorithms are presented for constructing 2-3 trees from sorted lists of data items. The two parallel algorithms are designed on a shared-memory SIMD computer; one, based on the EREW model, uses N/log log N processors and requires O(log log N) time and the other, based on the CREW model, uses N processors and requires O(1) time, where N is the number of data items in the input sorted list. © 1991.