Algorithm : Pipe Sort

Input : search lattice with A() and S() edge costs
for (level k = 0 to N -1 do begin
Generate-Plan( ) ;
for (each Group-by g in level k +1) do begin
Fix the sort order of g as the order of the
group by connected to g by an A() edge ;


Generate-Plan( )
Make k additional copies of each level k +1 vertex ;
Connect each copy vertex with the same set of level k vertices as the original vertex ;
Assign cost A(e_ij) to edge e_ij from the original vertex and S(e_ij) to edge from the copy vertex ;
Find minimum cost matching on the transformed levels.