# Reducing sorting to max-flow

Is there a linear-time reduction from the sorting problem to the max-flow problem?

If so, what would such a reduction look like?

It seems unlikely to me for information-theoretic reasons. Expressing the answer to a sorting problem requires $\Omega(n\log n)$ bits of information. On the other hand, the answer to a maximum flow problem on an $m$-edge graph can be expressed (via a network simplex formulation) using only $O(m)$ bits of information (which edges are saturated, which are unused, and which form a spanning tree of used but unsaturated edges). Similar arguments apply to minimum-cost flow, etc. So to make a flow problem that has enough information in the solution to recover the sorted order, you need $\Omega(n\log n)$ edges.

• Brilliant answer! Commented Jun 17, 2015 at 5:22
• @DavidEppstein Is this lower bound on some comparisonless model? Commented Aug 8, 2019 at 0:41
• It's a handwavy argument. You could make it rigorous in some sort of comparison tree model (because in such models bits of information in the output translate directly to number of comparisons needed in an algorithm) but the hard part would be devising a model in which the flow part made sense. Commented Aug 8, 2019 at 4:51