A couple of years ago I wrote an article about isotonic regression. Below is the link to the description of PAVA.
If $a$ is vector of input values, $w$ is vector of weights, $y$ is vector of output values minimizing $\sum_i w_i (y_i-a_i)^2$ subject to $y_1\leq ...\leq y_n$, the algorithm is:
Set a'=a, w'=w, j=1, S=0, S=1
For i=2 to n do:
a'[j] = a[i]
w'[j] = w[i]
while j>1 and a'[j] < a'[j-1] do
a'[j-1] = (w'[j]*a'[j] + w'[j-1]*a'[j-1]) / (w'[j] + w'[j-1])
w'[j-1] += w'[j]
S[j] = i
for k=1 to j do
for l=S[k-1]+1 to S[k] do
y[l] = a'[k]
Here S defines to which old points each new point corresponds.