Is it possible to "sort" a continuous function?

Question

I was motivated for this question while seeking for a new sorting algorithm.

Suppose a continuous function $f : [a, b] \to \mathbb{R}$ is given. I wanted to define the sorted version $g$ of $f$, which shall satisfy the following properties:

• $g$ monotone increases
• $g(a)$ is the global minimum of $f$
• $g(b)$ is the global maximum of $f$

And I eventually came up with the following equation: $$ \int_a^x g = \int_{\{y : f(y) \leq g(x)\}} f $$

And I tried to construct $g$ from $f$ explicitly. Simple argument: Since $\{y : f(y) \leq g(x)\}$ is a closed subset of the compact set $[a, b]$, it is the union of some finitely many closed intervals (and possibly some isolated points), say $[a_1(x) = a, b_1(x)], [a_1(x), b_1(x)], \cdots, [a_n(x), b_n(x) = b]$. That gives the following equation: $$ \int_a^x g = \sum_{k=1}^n\int_{a_k(x)}^{b_k(x)} f $$

By taking the derivative of both sides of the equation above, I get this: $$ g(x) = \sum_{k=1}^n (f(b_k(x)) \cdot b_k'(x) - f(a_k(x)) \cdot a_k'(x)) $$

By definition of $a_k$ and $b_k$, $f \circ a_k = f \circ b_k = g$, and thus: $$ g(x) = \sum_{k=1}^n (g(x) \cdot b_k'(x) - g(x) \cdot a_k'(x)) = \sum_{k=1}^n g(x) (b_k'(x) - a_k'(x)) = g(x) \sum_{k=1}^n (b_k'(x) - a_k'(x)) $$

...which doesn't give any information of $g$. Does this mean this equation is under-determined? Does it even make sense to "sort" a function?

Answer 1

I think what you want is the nondecreasing rearrangement of $f$ on the interval $[a,b]$, which can defined by $$g(x)=\inf\{t :m(\{s \in [a,b]:f(s)>t\})\le x-a\}$$ where $m$ is Lebesgue measure.

Answer 2

I think to do this properly, we need to quantify the amount of "stuff" at each height level. Intuitively, a higher slope (defined as the absolute value of the gradient) should correspond to less stuff, since we hang around at the relevant value for less time. For example, if we pass through a certain height very quickly, then in some sense there's fewer entries around that level. In light of this, I'd argue that $\mathrm{sorted}(f)$ should be defined as the unique increasing, differentiable function $g$ with the same range as $f$ such that for all $y$ in this range, the value $g'(g^{-1}(y))$ is somehow related to the multiset $|f'(f^{-1}(y))|.$ Intuitively, we can say that double the slope means half the stuff. Triple the slope means a third as much stuff, etc. Hence the reciprocal of the slope seems to be the right measure of the amount of "stuff". Ergo the formula $$\frac{1}{g'(g^{-1}(y))} = \sum_{x \in f^{-1}(y)} \frac{1}{|f'(x)|}$$ seems to be the right constraint on $g = \mathrm{sorted}(f)$. For the sake of uniqueness, we should probably also assume $$\mathrm{inf}(\mathrm{dom}(f)) = \mathrm{inf}(\mathrm{dom}(g)), \qquad \mathrm{sup}(\mathrm{dom}(f)) = \mathrm{sup}(\mathrm{dom}(g)).$$ For example, if $f(x) = \sqrt{1-x^2}, x \in [-1, 1]$, then $g(x) = \sqrt{1-(\frac{x-1}{2})^2}, x \in [-1, 1]$ should have the desired properties. I don't know how (or whether) this fits with Robert Israel's answer.

Good question, by the way.

Answer 3

Take some point on the $y$-axis. Call it $y_0$. Now expand that point out to an interval going from $y_0$ to $y_0+\Delta y$. Now draw two horizontal lines, one at $y_0$ and one at $y_0+\Delta y$. Now look at where the function in inside that band. Then mark out how much of the $x$-axis that portion of the function covers. In other words, look at "how many" $x$ values a change of $\Delta y$ covers. Then take the ratio of this to the size of the change. Then take the limit as this change goes to zero.

In other words, we have $\lim_{\Delta y \rightarrow 0}m(\{x: y_0<f(x)<y_0+\Delta y\})/\Delta y$.

This yields a different value for each $y_0$, and represents in some sense how "dense" $y$ values are. In fact, one interpretation is as a probability density: if $x$ is randomly chosen from $[a,b]$, then this gives the probability density for $f(x)$ being a particular value.

So if you want a "sorted" version of $f$, you'd want a function that is strictly increasing and that has the same density function as $f$. Proving that this exists and is unique is non-trivial, but given that, that gives you the desired function.