# Sorting strings and constructing digital search trees in parallel

Title | Sorting strings and constructing digital search trees in parallel |

Publication Type | Journal Articles |

Year of Publication | 1996 |

Authors | JaJa JF, Ryu K W, Vishkin U |

Journal | Theoretical Computer Science |

Volume | 154 |

Issue | 2 |

Pagination | 225 - 245 |

Date Published | 1996/02/05/ |

ISBN Number | 0304-3975 |

Abstract | We describe two simple optimal-work parallel algorithms for sorting a list L= (X1, X2, …, Xm) of m strings over an arbitrary alphabet Σ, where ∑i = 1m¦Xi¦ = n and two elements of Σ can be compared in unit time using a single processor. The first algorithm is a deterministic algorithm that runs in O(log2m/log log m) time and the second is a randomized algorithm that runs in O(logm) time. Both algorithms use O(m log m + n) operations. Compared to the best-known parallel algorithms for sorting strings, our algorithms offer the following improvements. 1.1. The total number of operations used by our algorithms is optimal while all previous parallel algorithms use a nonoptimal number of operations. |

URL | http://www.sciencedirect.com/science/article/pii/0304397594002630 |

DOI | 10.1016/0304-3975(94)00263-0 |