Median

In statistics, the median is that value that separates the highest half of the sample from the lowest half. To find the median, arrange all the observations from lowest value to highest value and pick the middle one. If there are an even number of observations, take the average of the two middle values. When we use the median to describe what the observations have in common, there are several choices for a measure of variability, the range, the interquartile range, and the absolute deviation[?]. Since the median is the same as the second quartile, its calculation is illustrated in the article on quartiles.

Even though sorting n items takes in general Θ(n log n) operations, by using a recursive "Divide-and-Conquer" algorithm the median of n items can be computed with only Θ(n) operations.

Calculation of medians is a popular technique in summary statistics and summarizing statistical data, since it is simple to understand and easy to calculate, while also giving a measure that is more robust in the presence of outlier values than is the mean.