On a "1-D line", the point that minimizes the sum of the distances is the median, WHY?

I should apologize for my earlier rude and incorrect comment.

Here is a rather tedious proof that the median is a minimizer of $\min_x f(x)$ ($f$ defined below):

I need some notation: Let the set of points by $d_1,...,d_n$, let $\Omega = \{d_k\}_k$ (some points may be repeated) and define $f(x) = \sum_k |x-d_k|$. If $R$ is a relation on $\mathbb{R}$, let $I_R(x) = \{ k \,|\, x R d_k \}$ (eg, $I_=(x)$ is the set of indices such that $d_k = x$).

We note that $f$ is convex, and we have $f(x) = \sum_{k \in I_<(x)}d_k-x + \sum_{k \in I_>(x)}x-d_k$. Since $f$ is continuous, we see that $f$ is piecewise linear (affine), and for $x \notin \Omega$, $f'(x) = |I_>(x)|-|I_<(x)|$. Furthermore, since $f$ is convex, $f'(x)$ is non-decreasing on $\Omega^C$.

For $x < \min_k d_k$, we have $f'(x) = -n$, and for $x > \max_k d_k$, we have $f'(x) = +n$. Hence the problem $\min_x f(x)$ has a minimum on $[\min_k d_k, \max_k d_k]$.

Let $\phi_1,...,\phi_m$ be the non-decreasing sequence of values that $f'$ takes on $\Omega^C$, and let $J_1,...,J_m$ be the corresponding open intervals. (We have $\phi_1 = -n, \phi_m = +n$, of course.) There are two case to consider:

Case (1): For some $k$, we have $\phi_k = 0$, and for $x \in J_k$, $|I_>(x)|=|I_<(x)|$. It follows that $n$ is even, and since the median lies in $J_k$, we see that the median is a minimizer (in fact, $x$ is a minimizer iff $x \in \overline{J_k}$).

Case (2): For some $k$, we have $\phi_k <0, \phi_{k+1} >0 $. Let $\hat{x}$ be the point separating $J_k, J_{k+1}$ (hence $\hat{x} \in \Omega$). Then $\hat{x}$ is the minimizer of $f$. For $x \in J_k$, we have $f'(x) = |I_>(\hat{x})|-|I_=(\hat{x})|-|I_<(\hat{x})|$, and for $x \in J_{k+1}$, we have $f'(x) = |I_>(\hat{x})|+|I_=(\hat{x})|-|I_<(\hat{x})|$, or, in other words, $$|I_=(\hat{x})| > \left| |I_>(\hat{x})|-|I_<(\hat{x})| \right| $$ To see why the median is $\hat{x}$, let $l=|I_>(\hat{x})|, p=|I_<(\hat{x})|$ and $e=|I_=(\hat{x})|$ ($l+e+p = n$, of course). The above shows that $e > |p-l|$. If $l+e+p$ is even, then let $k=\frac{1}{2}(e+p-l)>0$. Then we have $l+k = p+e-k$, from which it follows that the $l+k$th and $l+k+1$st (ordered) points are equal to $\hat{x}$, and hence $\hat{x}$ is the median.If $l+e+p$ is odd, then let $k=\frac{1}{2}(e+p-l-1)\geq 0$. Then the $l+k+1$st (ordered) point is equal to $\hat{x}$, and hence the median is equal to $\hat{x}$.

Alternative:

One may use the convex subdifferential to obtain the same characterization. A quick computation shows that $\partial f(x) = -\{|I_<(\hat{x})|\}+\{|I_>(\hat{x})|\}+[-|I_=(\hat{x})|,+|I_=(\hat{x})|]$, and $x$ is a minimizer iff $0 \in \partial f(x)$, or equivalently, $x$ is a minimizer iff $|I_=(\hat{x})| \geq \left| |I_>(\hat{x})|-|I_<(\hat{x})| \right| $. Then a little work (essentially the same as the cases above) shows that the median satisfies the latter characterization.