suponiendo que su tabla se llame cats, intente esto:
select * from cats
order by
case when parentid = 0 then id else parentid end,
case when parentid = 0 then 0 else id end
Actualizado para incluir cuándo el padre tendría una identificación más alta en comparación con los niños