Is the median a function?

Question

Suppose I have a list of values $S$ containing $$x_1, x_2,...,x_n$$ where each $x_i \in \Bbb R$. Suppose I order them from smallest to largest $$x_{(1)}, x_{(2)},...,x_{(n)}$$

Is there a function or an optimization problem that achieves this? Or is the median found only through a procedure of reordering?

Answer 1

A median is precisely a minimizer of the function $$t \mapsto \sum_{i=1}^{n}|t-x_i|.$$ (It may not be unique which is why I write a minimizer.) An optimization algorithm which does not reorder is described in Problem 1.4.11 of Kenneth Lange's MM Optimization Algorithms, SIAM.

Added: The algorithm proceeds as follows. Let $t_0$ be different from all the $x_i$. Given $k\in\{0,1,2,\ldots\}$ and $t_k$, set $w_{k,i} := 1/|t_k-x_{i}|$ and update $$t_{k+1} := \frac{\sum_{i=1}^{n}w_{k,i}x_i}{\sum_{i=1}^{n}w_{k,i}}.$$ I am not sure if this is faster than ordering, but it is interesting. There is even a variant not just for the median, but for quantiles.

Answer 2

You don't say any way, so I assume you are looking for an algorithm that a computer might implement to do the calculation.

There is a very simple algorithm that doesn't involve reordering the values. For simplicity, I'll describe the $n$ odd case.

• For each index $i$:
  • Count how many of the entries are less than $x_i$
  • Count how many of the entries are greater than $x_i$
  • Count how many of the entries are equal to $x_i$
  • If these counts are consistent with $x_i$ being the median, halt and output $x_i$

---

That said, I'm virtually certain this is an XY problem. You are only likely to get an answer that is useful for whatever goal you are trying to achieve if you ask a question about whatever goal you are trying to achieve. (which will likely require you to also specify the context you're working in as well)