Try this implementation for PAVA:

https://gist.github.com/gustavla/9499068

Also, how are you timing Python? When I run this on a sample size of 10 using IPython's %timeit, it takes a few microseconds, which is 2 orders of magnitude from what you report.