Projection gradient algorithms are simple and efficient methods for constraint optimization problems, but they are highly dependent on how fast the projecting subproblem can be solved. In this work, we study the problem of projecting onto a particular kind of constrains: order simplices, or called isotonic regression problem with respect to a complete order. We develop an $O(n)$ Primal-Dual algorithm that can begin from any given active set of the constrains. So when used to the series subproblems of projection gradient methods, it can benefit from former projections, and so exceeds the other existed methods.