respect to $y$, we get:
$d L_1(y)/y = \sum_i - \texttt{sign}(xs[i] - y)$

Recall that $d(|x|)/dx = \texttt{sign}(x)$
Hence, the best $y$ to minimize the $L_1$ norm is the value that makes the sum
of the signs $\sum_i \texttt{sign}(xs[i] - y)$ minimal. The median is perfect
for this optimization problem.
- When the list has an odd number of elements, say, $2k + 1$, $k$ elementswill have sign $-1$, the middle element will have sign $0$, and the $k$ elementsafter will have sign $+1$. The sum will be $0$ since half of the $-1$ and the $+1$cancel each other out.
- Similar things happen for even, except that we can get a best total sign distance of $+1$using either of the middle elements.

#### § Proof 2:

Math.se has a nice picture proof abot walking from left to right.
#### § Proof 3:

Consider the case where $xs$ has only two elements, with $xs[0] < xs[1]$.
Then the objective function to minimize the L1 norm, ie, to minimize
$|xs[1] - y| + |xs[2] - y|$. This is satisfied by any point in
between $xs[1]$ and $xs[2]$.
In the general case, assume that $xs[1] < xs[2] \dots < xs[N]$. Pick the smallest
number $xs[1]$ and the largest number $xs[N]$. We have that any $y$ between $xs[1]$
and $xs[N]$ satisfies the condition. Now, drop off $xs[1]$ and $xs[N]$, knowing
that we must have $y \in [xs[1], xs[N]]$. Recurse.
At the end, we maybe left with a single element $xs[k]$. In such a case, we need
to minimize $|xs[k] - y|$. That is, we set $xs[k] = y$.
On the other hand, we maybe left with two elements. In this case, any point between
the two elements is a legal element.
We may think of this process as gradually "trapping" the median between the
extremes, using the fact that that any point $y \in [l, r]$ minimizes
$|y - l| + |y - r|$!