An efficient parallel algorithm for the single function coarsest partition problem

We describe an efficient parallel algorithm to solve the single function coarsest partition problem. The algorithm runs in O(log n) time using O(n log log n) operations on the arbitrary CRCW PRAM. The previous best-known algorithms run in O(log2 n) time using O(n log2 n) operations on the CREW PRAM, and O(log n) time using O(n log n) operations on the arbitrary CRCW PRAM. Our solution is based on efficient algorithms for solving several subproblems that are of independent interest. In particular, we present efficient parallel algorithms to find a minimal starting point of a circular string with respect to lexicographic ordering and to sort lexicographically a list of strings of different lengths