The Pool Adjacent Violators Algorithm (PAVA) implementation that's currently in MLlib can take O(N!) time for certain inputs, when it should have worst-case complexity of O(N^2).
To reproduce this, I pulled the private method poolAdjacentViolators out of mllib.regression.IsotonicRegression and into a benchmarking harness.
Given this input
I vary the length of the input to get these timings:
|Input Length||Time (us)|
(tests were performed using https://github.com/sirthias/scala-benchmarking-template)
I can also confirm that I run into this issue on a real dataset I'm working on when trying to calibrate random forest probability output. Some partitions take > 12 hours to run. This isn't a skew issue, since the largest partitions finish in minutes. I can only assume that some partitions cause something approaching this worst-case complexity.
I'm working on a patch that borrows the implementation that is used in scikit-learn and the R "iso" package, both of which handle this particular input in linear time and are quadratic in the worst case.