An efficient parallel algorithm for building the separating tree

We present an efficient parallel algorithm for building the separating tree for a separable permutation. Our algorithm runs in O(log2n)O(log2n) time using O(nlog1.5n)O(nlog1.5n) operations on the CREW PRAM and O(log2n)O(log2n) time using O(nlognloglogn)O(nlognloglogn) operations on the COMMON CRCW PRAM.