 Pool adjacent violators algorithm

The pool adjacent violators algorithm solves weighted isotonic regression: minimize ${\sum }_i{w}_i(y_i-{\theta }_i{)}^2$ with $w_i>0$ and ${\theta }_1\le \cdots \le {\theta }_n$. Start with singleton blocks. Whenever consecutive fitted block means decrease, merge the two blocks and replace them by their weighted mean; continue until no violation remains. For equal weights and observations $(3,1,2)$, merging the first two gives the solution $(2,2,2)$. A stack implementation revisits each block only when merging it, giving linear time. Pooling is required by the order-constrained optimum: two reversed adjacent blocks cannot remain separate fitted levels.