結論

ソートで頑張っても、のオーダーであることは自明。少々の重い計算でも、ソートするくらいなら、逐一計算したほうがまし。ソートをせざるを得ないデータの出し方をせずに、工夫するのが、結局速い、か・・・。