Before revision:  We also present a second in-place EREW algorithm  that has linear work and span O(\log n \cdot \log \log n), which is within an O(\log\log n) factor of the optimal span.
After revision:  We also present a second in-place EREW algorithm for the partition problem that has linear work and span O(\log n \cdot \log \log n), which is within an O(\log\log n) factor of the optimal span.