Try this implementation for PAVA: https://gist.github.com/gustavla/9499068 https://gist.github.com/gustavla/9499068 Also, how are you timing Python? When I ru

Try this implementation for PAVA: https://gist.github.com/gustavla/9499068 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.