text:
Compute the Median
Challenge
Given a nonempty list of real numbers, compute its median.
Definitions
The median is computed as follows: First sort the list,

if the number of entries is odd, the median is the value in the center of the sorted list,
otherwise the median is the arithmetic mean of the two values closest to the center of the sorted list.

Examples
[1,2,3,4,5,6,7,8,9] -> 5
[1,4,3,2] -> 2.5
[1.5,1.5,1.5,1.5,1.5,1.5,1.5,1.5,1.5,-5,100000,1.3,1.4] -> 1.5
[1.5,1.5,1.5,1.5,1.5,1.5,1.5,1.5,1.5,1.5,-5,100000,1.3,1.4] -> 1.5

Can we output as a fraction over 2 (e.g.  7/2 or 8/2)

According to this fractions are fine.

How is this not already a challenge?

That is the very same I was wondering too.

If our language can't handle decimals can we assume input is only integers?

What if our language doesn't have lists? Can we use dynamically initialized arrays?

@wheatwizard as long as it producces the correct output, which might have decimals, thats ok!

@WadeTyler Yes, you can also use a variable number of arguments instead, for instance.

@orlp This is a subset of this challenge.

#Q, 3 bytes med Taken from here.

It's also makes a nice fastest code challenge as there are some interesting linear time algorithms.

I know this challenge is ancient, but You should add at least one test case with an even number of arguments where the mean over the complete array differs from the median; e.g. the 3rd case with an extra 1.5.

@Titus This is a very good point, thank you! I'll add some later today!

Python 2, 48 bytes
An unnamed function which returns the result. -1 byte thanks to xnor.
lambda l:l.sort()or(l[len(l)/2]+l[~len(l)/2])/2.

The first step is obviously to sort the array, using l.sort(). However, we can only have one statement in a lambda, so we utilise the fact that the sort function returns None by adding an or - as None is falsy in Python, this tells it to evaluate and return the next part of the statement.
Now we have the sorted list, we need to find either the middle, or the middle two, values.
Using a conditional to check the length's parity would be too verbose, so instead we get the indexes len(l)/2 and ~len(l)/2:

The first is floor(length / 2), which gets the middle element if the length is odd, or the left item in the central pair if the length is even.
The second is the binary inversion of the list length's, evaluating to -1 - floor(length / 2). Due Python's negative indexing, this essentially does the same as the first index, but backwards from the end of the array.

If the list is of odd length, these indexes will point to the same value. If it is of even length, then they will point to the central two items.
Now that we have these two indexes, we find these values in the list, sum them, and divide them by 2. The trailing decimal place in /2. makes sure that it is float division rather than integer division.
The result is implicitly returned, as this is a lambda function.
Try it online!

Looks like a lambda wins out despite the repetition: lambda l:l.sort()or(l[len(l)/2]+l[~len(l)/2])/2.

@xnor Thanks! When I tried that, I accidentally counted the f=, thinking it was 1 byte longer.

Python3 - 31 30 bytes
Saved a byte thanks to @Dennis!
I wasn't planning on a builtin answer, but I found this module and thought it was really cool cuz I had no idea it existed.
from statistics import*;median

Try it online here.

from statistics import*;median saves a byte.

@Dennis oh cool. is that always shorter?

It always beats using __import__, but import math;math.log would beat from math import*;log.

Brain-Flak, 914 + 1 = 915 bytes
([]){({}[()]<(([])<{({}[()]<([([({}<(({})<>)<>>)<><({}<>)>]{}<(())>)](<>)){({}())<>}{}({}<><{}{}>){{}<>(<({}<({}<>)<>>)<>({}<>)>)}{}({}<>)<>>)}{}<>{}>[()]){({}[()]<({}<>)<>>)}{}<>>)}{}([]<(()())>(<>))<>{(({})){({}[()])<>}{}}{}<>([{}()]{}<(())>){((<{}{}([[]]()){({}()()<{}>)}{}(({}){}<([]){{}{}([])}{}>)>))}{}{(<{}([[]]()()){({}()()<{}>)}{}({}{}<([]){{}{}([])}{}>)>)}{}([(({}<((((((()()()){}){}){}()){})[()()()])>)<(())>)](<>)){({}())<>}{}<>{}{}<>(({})){{}{}<>(<(())>)}{}(({}<>)<{(<{}([{}])>)}{}{(({})<((()()()()()){})>)({}(<>))<>{(({})){({}[()])<>}{}}{}<>([{}()]{})({}<({}<>)<>>((((()()()){}){}){}){})((()()()()()){})<>({}<>)(()()){({}[()]<([([({})](<()>))](<>())){({}())<>}{}<>{}{}<>(({})){{}{}<>(<(())>)}{}(({})<>)<>{(<{}([{}])>)}{}({}<>)<>({}<><({}<>)>)>)}{}({}(<>))<>([()]{()<(({})){({}[()])<>}{}>}{}<><{}{}>)<>(({}{}[(())])){{}{}(((<{}>)))}{}{}{(<{}<>([{}])><>)}{}<>}{}>){(<{}(((((()()()()())){}{})){}{})>)}{}

Requires the -A flag to run.
Try it online!
Explanation
The backbone of this algorithm is a bubble sort I wrote a while ago.
([]){({}[()]<(([])<{({}[()]<([([({}<(({})<>)<>>)<><({}<>)>]{}<(())>)](<>)){({}())<>}{}({}<><{}{}>){{}<>(<({}<({}<>)<>>)<>({}<>)>)}{}({}<>)<>>)}{}<>{}>[()]){({}[()]<({}<>)<>>)}{}<>>)}{}

I don't remember how this works so don't ask me.  But I do know it sorts the stack and even works for negatives
After everything has been sorted I find 2 times the median with the following chunk
([]<(()())>(<>))<>{(({})){({}[()])<>}{}}{}<>([{}()]{}<(())>)  #Stack height modulo 2
{((<{}{}          #If odd
 ([[]]())         #Push negative stack height +1
 {                #Until zero
  ({}()()<{}>)    #add 2 to the stack height and pop one
 }{}              #Get rid of garbage
 (({}){}<         #Pickup and double the top value
 ([]){{}{}([])}{} #Remove everything on the stack
 >)               #Put it back down
>))}{}            #End if
{(<{}                     #If even
  ([[]]()())              #Push -sh + 2
  {({}()()<{}>)}{}        #Remove one value for every 2 in that value
  ({}{}<([]){{}{}([])}{}>)#Add the top two and remove everything under them
>)}{}                     #End if

Now all that is left is to make convert to ASCII
([(({}<((((((()()()){}){}){}()){})[()()()])>)<(())>)](<>)){({}())<>}{}<>{}{}<>(({})){{}{}<>(<(())>)}{}(({}<>)<
{(<{}([{}])>)}{}  #Absolute value (put "/2" beneath everything)

{                 #Until the residue is zero
(({})<            #|Convert to base 10
((()()()()()){})  #|
>)                #|...
({}(<>))<>{(({})){({}[()])<>}{}}{}<>([{}()]{})
({}<({}<>)<>>((((()()()){}){}){}){})((()()()()()){})<>({}<>)
                  #|
(()()){({}[()]<([([({})](<()>))](<>())){({}())<>}{}<>{}{}<>(({})){{}{}<>(<(())>)}{}(({})<>)<>{(<{}([{}])>)}{}({}<>)<>({}<><({}<>)>)>)}{}({}(<>))<>([()]{()<(({})){({}[()])<>}{}>}{}<><{}{}>)<>(({}{}[(())])){{}{}(((<{}>)))}{}{}{(<{}<>([{}])><>)}{}<>
}{}               #|
>)
{(<{}(((((()()()()())){}{})){}{})>)}{}  #If it was negative put a minus sign

Jelly, 9 bytes
L‘HịṢµ÷LS

Try it online!
Explanation
I'm still getting the hang of Jelly... I wasn't able to find built-ins for either the median or the mean of a list, but it's very convenient for this challenge that Jelly allows non-integer indices into lists, in which case it will return a pair of the two closest values. That means we can work with half the input length as an index, and get a pair of values when we need to average it.
L          Get the length of the input.
 ‘         Increment it.
  H        Halve it. This gives us the index of the median for an odd-length list
           (Jelly uses 1-based indexing), and a half-integer between the two indices
           we need to average for even-length lists.
   ịṢ      Use this as an index into the sorted input. As explained above this will
           either give us the median (in case of an odd-length list) or a pair of
           values we'll now need to average.
     µ     Starts a monadic chain which is then applied to this median or pair...
      ÷L     Divide by the length. L treats atomic values like singleton lists.
        S    Sum. This also treats atomic values like singleton lists. Hence this
             monadic chain leaves a single value unchanged but will return the
             mean of a pair.

Of course, Æṁ will work now

Actually, 1 byte
║

Try it online!

Right tool for the job.

R, 6 bytes
median

Not surprising that R, a statistical programming language, has this built-in.

R beating Jelly :D:D:D

Matlab/Octave, 6 bytes
A boring built-in:
median

Try it online!

I forget the rules for anonymous functions in MATLAB/Octave, should this be @median?

@Giuseppe I don't know what the currently accepted way to score built-in functions is.

Octave, 38 bytes
@(x)mean(([1;1]*sort(x))(end/2+[0 1]))

This defines an anonymous function. Input is a row vector.
Try it online!
Explanation
            sort(x)                 % Sort input x, of length k
      [1;1]*                        % Matrix-multiply by column vector of two ones
                                    % This vertically concatenates sort(x) with
                                    % itself. In column-major order, this effectively
                                    % repeats each entry of sort(x)
     (             )(end/2+[0 1])   % Select the entry at position end/2 and the next.
                                    % Entries are indexed in column-major order. Since
                                    % the array has 2*k elements, this picks the k-th
                                    % and (k+1)-th (1-based indexing). Because entries
                                    % were repeated, for odd k this takes the original
                                    % (k+1)/2-th entry twice. For even k this takes
                                    % the original (k/2)-th and (k/2+1)-th entries
mean(                            )  % Mean of the two selected entries

Ugh... clever use of "bsxfun" and mean :-)

Why not use median directly? 6 bytes: median

@Hunaphu Because flawr did it first :-)

I prefer this and always prefer non-builtins. Here is 37-byte edit without mean (36 with mean).

@Hunaphu Nice! Or 1 byte shorter by moving ' outside of concatenation

I think you can remove the last ' as well? Realizing this inspired an update to my answer so thanks!

@Hunaphu Ah, yes, you can!

APL (Dyalog Unicode), 14 bytes
≢⊃2+/2/⊂∘⍋⌷÷∘2

Try it online!
This is a train. The original dfn was {(2+/2/⍵[⍋⍵])[≢⍵]÷2}.
The train is structured as follows
┌─┼───┐
≢ ⊃ ┌─┼───┐
    2 / ┌─┼───┐
    ┌─┘ 2 / ┌─┼─┐
    +       ∘ ⌷ ∘
           ┌┴┐ ┌┴┐
           ⊂ ⍋ ÷ 2

⊢ denotes the right argument.
⌷ index

⊂∘⍋ the indices which indexed into ⊢ results in ⊢ being sorted
÷∘2 into ⊢ divided by 2

2/ replicate this twice, so 1 5 7 8 becomes 1 1 5 5 7 7 8 8
2+/ take the pairwise sum, this becomes (1+1)(1+5)(5+5)(5+7)(7+7)(7+8)(8+8)
⊃ from this pick

≢ element with index equal to the length of ⊢

Previous solutions
{.5×+/(⍵[⍋⍵])[(⌈,⌊).5×1+≢⍵]}
{+/(2/⍵[⍋⍵]÷2)[0 1+≢⍵]}
{+/¯2↑(1-≢⍵)↓2/⍵[⍋⍵]÷2}
{(2+/2/⍵[⍋⍵])[≢⍵]÷2}
{(≢⍵)⊃2+/2/⍵[⍋⍵]÷2}
≢⊃2+/2/2÷⍨⊂∘⍋⌷⊢
≢⊃2+/2/⊂∘⍋⌷÷∘2

MATL, 4 bytes
.5Xq

This finds the 0.5-quantile, which is the median.
Try it online!

I was just about to figure it out!

Ah no, I mean I was figuring out how to do it in MATL=) (But I had a 5 byte solution, so yeah...)

@flawr Post it then! It will surely be more interesting than mine

Nope, it was the same as yours just with an i in front :)

@flawr The same i that you suggested to make implicit? :-P

Exactly, I thought the order of the arguments is the other way around :)

@flawr Ah, ok :-) In general, except in some well-justified cases, the order of inputs is the same as in Matlab

Pyth - 11 bytes
Finds the average of the middle item taken both backwards and forwards.
.O@R/lQ2_BS

Test Suite.

JavaScript, 57 52 bytes
v=>(v.sort((a,b)=>a-b)[(x=v.length)>>1]+v[--x>>1])/2

Sort the array numerically.  If the array is an even length, find the 2 middle numbers and average them.  If the array is odd, find the middle number twice and divide by 2.

I've found that Array.sort() doesn't work properly with decimals

It does if you pass in a sorting function as I did.  If you call Array.sort() with no parameters, it uses an alphabetic sort.

Interesting. Didn't know that

You can save a few bytes by using the return value of sort() directly and getting rid of the t variable: v=>(v.sort((a,b)=>a-b)[(x=v.length)>>1]+v[--x>>1])/2

(x-1 also works, since both it and --x have higher precedence than >>.)

Thanks @Arnauld, that works great since sort both updates the v variable and also returns the sorted results.  You also used the bit shift operator which divides by 2 and truncates in one operation.

Not that you should necessarily correct for this, but if x>=2**31, this would fail. >> is a sign-propagating right shift, meaning that when the number is interpreted as a 32 bit integer, if the msb is set, then it stays set, making the result negative for 2**32>x>=2**31. For x>=2**32, it just yields 0.

Good observation @PatrickRoberts.

Mathematica, 6 bytes
Median

As soon as I figure out Mthmtca, I'm posting a solution in it.

In Mthmtca 0.1/10.1.0.0, the code would have the bytes CBC8 (ËÈ). However, until I apply another patch, the notion of function-calling might not meet PPCG's standards.

Perl 6, 31 bytes
*.sort[{($/=$_/2),$/-.5}].sum/2

Try it
Expanded:
*\     # WhateverCode lambda ( this is the parameter )

.sort\ # sort it

[{     # index into the sorted list using a code ref to calculate the positions

  (
    $/ = $_ / 2 # the count of elements divided by 2 stored in ｢$/｣
  ),            # that was the first index

  $/ - .5       # subtract 1/2 to get the second index

                # indexing operations round down to nearest Int
                # so both are effectively the same index if given
                # an odd length array

}]\

.sum / 2        # get the average of the two values

24 bytes

TI-Basic, 2 bytes
median(Ans

Very straightforward.

Ans is not an allowed I/O method.

@Mego your link and comment confuses me... according to the vote, it is allowed. Am I missing something?

@PatrickRoberts There's actually some debate currently about the threshold for acceptability. Several users (myself included) have been following the rule that a method needs at least +5 and at least twice as many upvotes as downvotes, which was the rule originally stated in that post (it's been removed since), and is the rule followed for standard loopholes.

Whoever removed my comment twice from my own post is annoying. Since there's no clearly accepted rule on acceptability, I don't see the problem here. You can see my answers on SO for how this is used as arguments to a program.

@Mego +38 is more than twice -18

@Timtech 6 months ago, when I made the comment, that was not the case.

J, 16 14 bytes
2%~#{2#/:~+\:~

Try it online!
In addition to BMO's array duplication trick, I found that we can add the whole array sorted in two directions. Then I realized that the two steps can be reversed, i.e. add the two arrays, then duplicate them and take the nth element.
How it works
2%~#{2#/:~+\:~
                Input: array of length n
       /:~      Sort ascending
           \:~  Sort descending
          +     Add the two element-wise
     2#         Duplicate each element
   #{           Take n-th element
2%~             Halve

Previous answers
J with stats addon, 18 bytes
load'stats'
median

Try it online!
Library function FTW.
median's implementation looks like this:
J, 31 bytes
-:@(+/)@((<.,>.)@(-:@<:@#){/:~)

Try it online!
How it works
-:@(+/)@((<.,>.)@(-:@<:@#){/:~)
         (<.,>.)@(-:@<:@#)       Find center indices:
                  -:@<:@#          Compute half of given array's length - 1
          <.,>.                    Form 2-element array of its floor and ceiling
                          {/:~   Extract elements at those indices from sorted array
-:@(+/)                          Sum and half

A bit of golfing gives this:
J, 28 bytes
2%~[:+/(<.,>.)@(-:@<:@#){/:~

Try it online!

Nicely done, the J port of my APL answer would be #{0,2+/\2#-:/:] at a close 15 bytes (man I miss ⎕io).

C++ 112 Bytes
Thanks to @original.legin for helping me save bytes.
#include<vector>
#include<algorithm>
float a(float*b,int s){std::sort(b,b+s);return(b[s/2-(s&1^1)]+b[s/2])/2;}

Usage:
    int main()
    {
        int n = 4;
        float e[4] = {1,4,3,2};
        std::cout<<a(e,n); /// Prints 2.5

        n = 9;
        float e1[9] = {1,2,3,4,5,6,7,8,9};
        std::cout<<a(e1,n); /// Prints 5

        n = 13;
        float e2[13] = {1.5,1.5,1.5,1.5,1.5,1.5,1.5,1.5,1.5,-5,100000,1.3,1.4};
        std::cout<<a(e2,n); /// Prints 1.5

        return 0;
    }

You could use float instead of double to save two bytes. Also, on GCC, you can use #import<vector> and #import<algorithm> instead of #include. (Note that you don't need the space after either the #include or #import)

@Steadybox I didn't count the two includes in the score. Should I? Also, I mainly use Clang so I don't know much about GCC but thanks.

Yes, the includes should be included in the byte count if the code doesn't compile without them.

C#, 126 bytes
using System.Linq;float m(float[] a){var x=a.Length;return a.OrderBy(g=>g).Skip(x/2-(x%2==0?1:0)).Take(x%2==0?2:1).Average();}

Pretty straightforward, here with LINQ to order the values, skip half the list, take one or two values depending on even/odd and average them.

You need to include using System.Linq;  into your byte count, however you can cancel this out by making some changes. Compile to a Func<float[], float> and assign the value of the modulo to a variable for 106 bytes: using System.Linq;a=>{int x=a.Length,m=x%2<1?1:0;return a.OrderBy(g=>g).Skip(x/2-m).Take(++m).Average();};

@TheLethalCoder I'm never quite sure what constitutes a complete program. You are right about the using. Concatenating the declarations of the modulus with the length is also a good idea. I experimented around a bit with that but couldn't get it to be shorter than putting it twice in there. I would venture to say that your optimizations are worth an answer by itself, as they are quite substantial and I would not have come up with them.

The challenge doesn't state that you need a full program so an anonymous method is fine. Beyond that I only stated some common golfing tips so no need for me to add an answer just golf your own!

Common Lisp, 89
(lambda(s &aux(m(1-(length s)))(s(sort s'<)))(/(+(nth(floor m 2)s)(nth(ceiling m 2)s))2))

I compute the mean of elements at position (floor middle) and (ceiling middle), where middle is the zero-based index for the middle element of the sorted list. It is possible for middle to be a whole number, like 1 for an input list of size 3 such as (10 20 30), or a fraction for lists with an even numbers of elements, like 3/2 for (10 20 30 40). In both cases, we compute the expected median value.
(lambda (list &aux
             (m (1-(length list)))
             (list (sort list #'<)))
  (/ (+ (nth (floor m 2) list)
        (nth (ceiling m 2) list))
     2))

Vim, 62 bytes
I originally did this in V using only text manipulation until the end, but got frustrated with handling [X] and [X,Y], so here's the easy version.  They're about the same length.
c$:let m=sort(")[(len(")-1)/2:len(")/2]
=(m[0]+m[-1])/2.0

Try it online!
Unprintables:
c$^O:let m=sort(^R")[(len(^R")-1)/2:len(^R")/2]
^R=(m[0]+m[-1])/2.0

Honorable mention:

^O takes you out of insert mode for one command (the let command).
^R" inserts the text that was yanked (in this case the list)

Husk, 10 bytes
½ΣF~e→←½OD

Try it online!
Explanation
This function uses that the median of \$[a_1 \dots a_N]\$ is the same as the median of \$[a_1 \; a_1 \dots a_N \; a_N]\$ which avoids the ugly distinction of odd-/even-length lists.
½ΣF~e→←½OD  -- example input: [2,3,4,1]
         D  -- duplicate: [2,3,4,1,2,3,4,1]
        O   -- sort: [1,1,2,2,3,3,4,4]
       ½    -- halve: [[1,1,2,2],[3,3,4,4]]
  F         -- fold the following
   ~        -- | compose the arguments ..
     →      -- | | last element: 2
      ←     -- | | first element: 3
    e       -- | .. and create list: [2,3]
            -- : [2,3]
 Σ          -- sum: 5
½           -- halve: 5/2

Unfortunately ½ for lists has the type [a] -> [[a]] and not [a] -> ([a],[a]) which doesn't allow F~+→← since foldl1 needs a function of type a -> a -> a as first argument, forcing me to use e.

Fig, \$11\log_{256}(96)\approx\$ 9.054 bytes
KY
HSt2s{HL

Try it online!
-3 chars because bugfixes
KY
HSt2s{HL
--------
KY       # First helper function
 Y       # Interleave with self
K        # Sort
-------- # Send the result to the next function:
HSt2s{HL # Main function
     {HL # Compute len(input)/2-1
    s    # Drop that many items from the input
  t2     # Take 2
 S       # Sum
H        # Halve

J, 19 bytes
<.@-:@#{(/:-:@+\:)~

Explanation:
        (        )~   apply monadic argument twice to dyadic function
         /:           /:~ = sort the list upwards
               \:     \:~ = sort the list downwards
           -:@+       half of sum of both lists, element-wise
<.@-:@#               floor of half of length of list
       {              get that element from the list of sums

You can save a byte by removing the parentheses and applying ~ directly to each <.@-:@#{/:~-:@+\:~

JavaScript, 273 Bytes
function m(l){a=(function(){i=l;o=[];while(i.length){p1=i[0];p2=0;for(a=0;a<i.length;a++)if(i[a]<p1){p1=i[a];p2=a}o.push(p1);i[p2]=i[i.length-1];i.pop()}return o})();return a.length%2==1?l[Math.round(l.length/2)-1]:(l[Math.round(l.length/2)-1]+l[Math.round(l.length/2)])/2}

You should use arrow functions instead of using the function keyword. You can save a lot that way. Also, you can use ternaries instead of if statements. Instead of Math.round, you can use the bitwise OR operator: yourNumber | 0. For repeated properties uses (e.g. i.length), assign it to a 1-letter variable. All this will probably cut down your bytes by half ;)

Java 7, 99 bytes
Golfed:
float m(Float[]a){java.util.Arrays.sort(a);int l=a.length;return l%2>0?a[l/2]:(a[l/2-1]+a[l/2])/2;}

Ungolfed:
float m(Float[] a)
{
    java.util.Arrays.sort(a);
    int l = a.length;
    return l % 2 > 0 ? a[l / 2] : (a[l / 2 - 1] + a[l / 2]) / 2;
}

Try it online

I'm a bit disappointed even Java 7 has a short enough sorting syntax that https://en.wikipedia.org/wiki/Selection_algorithm#Partial_selection_sort is suboptimal

Dont you need to count the import for java.util.Arrays?

Whoops, thank you for noticiting. :)

Hello from the future! You can save 14 bytes by using integer division truncation to handle length parity. See my Java 8 answer.

Pari/GP - 37  39  Bytes
Let a be a rowvector containing the values.
b=vecsort(a);n=#b+1;(b[n\2]+b[n-n\2])/2  \\ 39 byte

n=1+#b=vecsort(a);(b[n\2]+b[n-n\2])/2    \\ obfuscated but only 37 byte

Since Pari/GP is interactive, no additional command is needed to display the result.

For the "try-it-online" link a line before and after is added. To get printed, the median-result in stored in variable w
a=vector(8,r,random(999))
n=1+#b=vecsort(a);w=(b[n\2]+b[n-n\2])/2
print(a);print(b);print(w)

Try it online!

Japt, 20 bytes
n gV=0|½*Ul)+Ug~V)/2

Test it online! Japt really lacks any built-ins necessary to create a really short answer for this challenge...
Explanation
n gV=0|½*Ul)+Ug~V)/2  // Implicit: U = input list
n                     // Sort U.
   V=0|½*Ul)          // Set variable V to floor(U.length / 2).
  g                   // Get the item at index V in U.
            +Ug~V     // Add to that the item at index -V - 1 in U.
                 )/2  // Divide by 2 to give the median.
                      // Implicit: output result of last expression

dc, 120 122 bytes
9kzsa0si[li:sli1+dsila>A]dsAx[1scddd;sr1-;sli:sr1-:s]sR[lidd1-;sr;s<R1+dsila>S]sS[1si0sclSxlc1=M]dsMxla2/dd1%-;sr.5-;s+2/p

Try it online!
My original code worked for all the provided test cases, but was actually faulty, so +2 bytes for the fix. Dang!
Lots of bytes since dc doesn't have any inbuilt sorting mechanism, and very little in the way of stack manipulation.
9k sets the precision to 9 places since we need the possibility of digits past the decimal point. dc doesn't float, so hopefully this is satisfactory.
zsa0si[li:sli1+dsila>A]dsAx dumps the entirety of the stack into array s, and preserves the number of items in register a.
Macros M, S, and R all make up a bubble sort. M is our 'main' macro, so to speak, so I'll cover that one first.
[1si0sclSxlc1=M]dsMx We reset increment register i to 1, and check register c to 0. We run macro S, which is one pass through the array. If S (actually, R, but S by proxy) made any changes, it would have set register c to one, so if this is the case we loop through M again.
[lidd1-;sr;s<R1+dsila>S]sS One pass through the array. We load the increment counter i, duplicate it twice, and decrement the top version of it by one. Essentially i is always high, so we compare i and i-1. Load the two values from array s, compare them, and if they're going the wrong way we run our swapping macro, R. Then we keep on incrementing i, comparing it to a, and running S until that comparison tells us we've hit the end of our array.
[1scddd;sr1-;sli:sr1-:s]sR An individual instance of swappery in array a. First we set our check register c to 1 so that M knows we made changes to the array. i should still be on the stack from earlier, so we duplicate it three times. We retrieve i indexed item from a, swap our top-of-stack so that i is present again, subtract one from it, and then retrieve that item from a. Here we run into a stack manipulation limitation, so we have to load i again and we store our previous i-1 value into that index in a. Now we just have our old i-indexed a value on the stack and i itself, so we swap these, subtract 1 from i, and replace the value in a.
Eventually M will stop running when it sees no changes have been made, and now that things are sorted we can do the actual median operation.
la2/dd1%-;sr.5-;s+2/p Since a already has the length of array s, we load it and divide by two. Testing for evenness would be costly, so we rely on the fact that dc uses the floor of a non-whole value for its index. We divide a by two and duplicate the value. We then get from s the values indexed by (a/2-.5) and (a/2-((a/2)mod 1)). This gives us the middle value twice for an odd number of values, or the middle two values for an even number. +2/p averages them and prints the result.

Java 8, 71 bytes
Parity is fun! Here's a lambda from double[] to Double.
l->{java.util.Arrays.sort(l);int s=l.length;return(l[s/2]+l[--s/2])/2;}

Nothing too complex going on here. The array gets sorted, and then I take the mean of two numbers from the array. There are two cases:

If the length is even, then the first number is taken from just ahead of the middle of the array, and the second number is taken from the position before that by integer division. The mean of these numbers is the median of the input.
If the length is odd, s and s-1 both divide to the index of the middle element. The number is added to itself and the result divided by two, yielding the original value.

Try It Online

Jelly, 2 bytes
Æṁ

Try it online!

SmileBASIC, 45 bytes
DEF M A
L=LEN(A)/2SORT A?(A[L-.5]+A[L])/2
END

Gets the average of the elements at floor(length/2) and floor(length/2-0.5)
Very simple, but I was able to save 1 byte by moving things around:
DEF M A
SORT A    <- extra line break
L=LEN(A)/2?(A[L-.5]+A[L])/2
END

GolfScript, 27 25 20 17 bytes
~..+$\,(>2<~+"/2"

Takes input as an array of integers on stdin. Outputs as an unreduced fraction. Try it online!
Explanation
The median of the array, as BMO's Husk answer explains, is equal to the median of an array twice as long where each element is repeated twice. So we concatenate the array to itself, sort, and take the mean of the middle two elements. If the length of the original array is \$l\$, the middle two elements of the doubled array are at indices \$l-1\$ and \$l\$.
~                  Evaluate input (converting string -> array)
 ..                Duplicate twice
   +               Concatenate two of the copies
    $              Sort the doubled array
     \,            Swap with the non-doubled array and get its length: l
       (           Decrement: l-1
        >          Array slice: all elements at index (l-1) and greater
         2<        Array slice: first two elements (originally at indices l-1 and l)
           ~       Dump array elements to stack
            +      Add
             "/2"  Push that string
                   Output all items on stack without separator

The output will be something like 10/2.

R without using the median builtin, 51 bytes
function(x,n=sum(x|1)+1)mean(sort(x)[n/2+0:1*n%%2])

Try it online!

function(x)mean(x,.5)

Python 3, 59 bytes
f=lambda l:l.sort()or(len(l)<3)*(l[0]+l[-1])/2or f(l[1:-1])

Try it online!
This is a recursive version:

the list is sorted
if there are 1 or 2 elements left, we output the median since 0  and -1 are both first and last with a single or atwo element list
if not, we remove first and last elements and call f.

Vyxal, 6 bytes
s∆ṁwfṁ

Try it Online!
sort the input, get the ∆ṁiddle item(s), wrap in a list, flatten and get the ṁean of that. (wf is needed to handle cases where the list is of odd length)
Or, without a trivial built-in
Vyxal, 11 bytes
L‹½₍⌈⌊$s$İṁ

Try it Online!
Explained
L‹½₍⌈⌊$s$İṁ
L‹         # Length of the input - 1 (this accounts for 0 indexing)
  ½        # halved
   ₍⌈⌊      # a list of the ceiling and floor of that number
     $s    # the input list sorted
       $İ  # indexed at the positions in the ceil,floor list
         ṁ # take the average of that

Racket 113 bytes
(let*((L(sort L >))(n(length L))(r list-ref))(if(odd? n)(r L(floor(/ n 2)))(/(+(r L(-(/ n 2)1))(r L(/ n 2)))2)))

Ungolfed:
(define (median L)
  (let* ((L (sort L >))
         (n (length L))
         (lr list-ref))
    (if (odd? n)
        (lr L (floor (/ n 2)))
        (/(+ (lr L (sub1(/ n 2)))
             (lr L (/ n 2)))
          2))))

Testing:
(median '(1 2 3))
(median '(1 2 3 4))

Output:
2
2 1/2

T-SQL, 101 67
DECLARE @ table(i real)
INSERT @ values(1),(3),(20),(4)

SELECT top 1PERCENTILE_CONT(.5)WITHIN GROUP(ORDER BY i)OVER()FROM @

Try it out

Clojure, 65 bytes
#(/(apply +(take 2(drop(-(count %)1)(sort(for[c % i[0 1]]c)))))2)

An other approach I tried:
#(apply +(map *(for[i(range)](get{-2 0.5 -1 1 0 0.5}(-(* i 2)(count %))0))(sort %)))

CJAM - 21
q~]$__,2/=\_,(2/=+2d/

q~] reads input to array
$__ sorts it and makes 2 copies
, gets length of array
2/ divides that by 2 rounded down
= finds the number at that index
/_ puts original array at top of stack and copies it
,( gets length of array - 1
2/ divides that by 2 rounded down
= finds the number at that index
+ adds the two array elements extracted 2d/ divides them by 2
as a double (so no rounding)

If the number of array elements N is odd, floor(N/2) = floor((N-1)/2). If N is even the two center elements are selected and the mean is found.
Longer but working alternative strategies:
q~]$__,2/)<_,@W%<&_:+\,d/
q~]$:A,2/_(A,2%$A=@A=+2d/\;
q~]$_Vf*_,2/.5t_W%.+.*:+

Haxe, 104 bytes
Not amazing, what with the function keywords and a mandatory sorting function …
function f(l,?a)return(l[(a={l[0]+=.0;l.sort(function(x,y)return x>y?1:-1);l.length;})>>1]+l[a-1>>1])/2;

With some whitespace:
function f(l, ?a)
  return (
      l[(a = {
          l[0] += .0;
          l.sort(
               function(x, y) return x > y ? 1 : -1
             );
          l.length;
        }) >> 1]
      + l[a - 1 >> 1]
    ) / 2;

I used l[0]+=.0; to let Haxe know the type of l. The alternative would be l:Array<Float> in the arguments. Then l is sorted, its length is stored in a, and then we basically do (l[a / 2] + l[(a - 1) / 2]) / 2.

So much abuse of Haxe's "everything is an expression" paradigm going on here, I love it.

Swift, 93 bytes
let m:([Double])->Double={{c,s in c%2==0 ?(s[c/2-1]+s[c/2])/2:s[c/2]}($0.count,$0.sorted())}

This takes about 10 seconds to compile on my machine but it works. It declares the constant m of type [Double] -> Double.

8th, 108 105 93 bytes
: m ' n:cmp a:sort a:len 2 n:/mod swap not if n:1- 2 a:slice a:open n:+ 2 n:/ else a:@ then ;

SED (Stack Effect Diagram) is a -- a n
Test
[1.5,1.5,1.5,1.5,1.5,1.5,1.5,1.5,1.5,-5,100000,1.3,1.4] m .

Output
1.50000

Ungolfed version (with comments)
\ Median
: m \ a -- a n
    ' n:cmp a:sort \ Sort array
    a:len          \ Get array length
    2 n:/mod       \ Remainder and quotient
    swap           \ Remainder on TOS
    not if
        \ Array contains an even number of items
        \ Get arithmetic mean of the two values closest to the center of the sorted list
        n:1- 2 a:slice a:open n:+ 2 n:/
    else
        \ Array contains an odd number of items
        \ Get the central value
        a:@
    then ;

C#, 75 bytes
a=>{Array.Sort(a);int m=a.Length;return m%2>0?a[m/2]:(a[m/2-1]+a[m/2])/2;};

An anonymous function which computes the median.
Full program with ungolfed method and test cases:
using System;

public class Program
{
    public static void Main()
    {
        Func<double[],double> f =
        a =>
        {
            Array.Sort(a);  // built-in sort function for arrays
            int m = a.Length;   // stores the number of elements from the array
            return m % 2 > 0 ? a[m/2] : ( a[m/2-1] + a[m/2] ) / 2;
            // if the array has an odd number of elements, the central number will be returned
            // otherwise, the average of the two central elements
        };

        // test cases:
        Console.WriteLine(f(new double[]{1,2,3,4,5,6,7,8,9}));  // 5
        Console.WriteLine(f(new double[]{1,4,3,2}));    // 2.5
        Console.WriteLine(f(new double[]{1.5,1.5,1.5,1.5,1.5,1.5,1.5,1.5,1.5,-5,100000,1.3,1.4}));  // 1.5
    }
}

It should be System.Array not just Array

PHP, 70 77 bytes
Not exactly optimal but works.
Requires that the values are passed over GET.
<?sort($_GET);die(($C=count($G=$_GET))&1?$G[~-$C/2]:($G[$C/2]+$G[$C/2-1])/2);

The result will be displayed in the browser and as the return code.

Thanks to Titus for fixing it, at the cost of 7 bytes.

You have a typo: ~~ should be ~-. 2) You compute the arithmetic mean of the whole array, but should only "of the two values closest to the center"; i.e. ?$G[~-$C/2]:($G[$C/2]+$G[$C/2-1])/2.

Thank you for the fix. It is sad that it got longer :/

Ruby 50 48 Bytes
-2 bytes thanks to @Conor O'Brien
->(l){l.sort!;e=l.length;(l[~-e/2]+l[e/2])/2.0}

You could save two bytes by removing the parentheses around the first l, and say ~-e instead of (e-1).

Racket, 95 bytes
Using the trusty old match syntax. The pattern (list _ m ... _) matches the middle of a list (that is, it omits the first and last element).
(λ(l)(let f([l(sort l <)])(match l[(list x)x][(list x y)(/(+ x y)2)][(list _ m ... _)(f m)])))

Ungolfed
(λ (l)
  (let f ([l (sort l <)])
    (match l
      [(list x) x]
      [(list x y) (/ (+ x y) 2)]
      [(list _ m ... _) (f m)])))

Perl 5, 58 + 2 (-ap) = 60 bytes
$_=(@F=sort{$a<=>$b}@F)%2?@F[@F/2]:@F[@F/2]/2+@F[@F/2-1]/2

Try it online!
Input is split into the @F array by the '-a' flag.  @F gets sorted.  Then, its length is checked to see if it is odd or even.  If odd, result is the middle element.  If even, result is half of the element to the left of middle plus half of the element to the right of the middle.

Julia 0.6.0 (9 bytes) (6 bytes)
median(a)
median
where a is an array. It's not a very exciting answer but it's cool that Julia has a built in function for the median.
edit: I didn't know I could just write median!

You can use median and count it as 6 bytes!

I didn't know thanks a lot!

APL, 26 bytes
{3>≢⍵:(+/÷≢)⍵⋄∇1↓¯1↓⍵[⍋⍵]}

Try it online!
How?

3>≢⍵:(+/÷≢)⍵ - if the length of the array is less then 3, return the average
⋄ - otherwise
∇1↓¯1↓⍵[⍋⍵] - return the sorted array with the first and last elements removed.

How is this the first APL answer?

GolfScript, 44 bytes
~$.,:l;~l 2%{l 2/$}{{l 2/$}2*+'/2'+}if{\;}l*

Try it online!
Explanation
~$.,:l;~l 2%{l.2/-}{{l 2/$}2*+'/2'+}if{\;}l*   |
~                                              Create array from input string
 $                                             Sort array
  .                                            Duplicate array
   ,                                           Pop and count the top array
    :l                                         Assign variable l
      ;                                        Pop
       ~                                       Convert array into individual integers
        l                                      Push variable l onto stack
          2%                                   Push 2 and perform mod
            {l 2/$}                            If block
            {l 2/                              push variable l and divide by 2
                 $}                            Copy/push value at index (push(stack[pop()]))
                   {{l 2/$}2*+'/2'+}           Else block
                    {l 2/                      Push l/2
                         $}                    Copy
                           2*                  Perform block {} twice
                             +                 Add top two of stack (result of copies)
                              '/2'+}if         Push and add '/2'. End if
                                      {\;}     New block. Swap top two elements then pop
                                          l*   Perform previous block l times

k, 23 bytes
Basically a slightly golfed version of q's canonical med in k.
{avg x(<x)@_.5*-1 0+#x}

Haskell 1.2 (Gofer), 44 bytes
f[x]=x
f[x,y]=(x+y)/2.0
f(x:y)=f.init$sort y

Try it online!

05AB1E, 2 bytes
Åm

Try it online or verify all test cases.
No need for an explanation, since Åm is a builtin which will:

Median. Sorts the list, then returns either the middle element or the average of the middle elements depending on the parity of the length of the list.

Lua, 64 63 bytes
function f(t)table.sort(t)h=#t//2return(t[h+1]+t[h+#t%2])/2 end

Try it online!
Sort table, get the position halfway through the table by integer-dividing table length by two, return average of element at half position plus one and element at half position if table length is even, else at half position plus one.
This solution is only valid in Lua 5.3 and onwards where there is integer division, // (and where integers can be squished right next to the keyword return). In Lua 5.1, the equivalent is math.floor(a/b), which would add several bytes.

You can remove the space between 2 and return

Thanks! I didn't try that, though I noticed before that integer plus keyword (with no intervening space) sometimes works in Lua 5.3; for instance if 0then end is valid.

I think the rule is that the keyword can't start with a letter that might make the number look like a hexadecimal. For example, you can't remove spaces before end, do, else etc.

Oh yeah, the lexer segments 0end as 0e, nd because it starts by simply reading a series of hexadecimal digits, decimal dots, or exponent markers into the buffer. So that part of the process accepts things like 1e+10e-10 or 1.1.1 before trying to get their numerical value and throwing a "malformed number" error.

Tcl, 100 bytes
proc M L {expr ([lindex [set S [lsort -r $L]] [set h [expr [llength $L]/2]]]+[lindex $S end-$h])/2.}

Try it online!

Tcl, 97 bytes
proc M L {expr ([lindex [set S [lsort $L]] [set h [expr [llength $L]/2]]]+[lindex $S end-$h])/2.}

Try it online!

Tcl, 123 bytes
proc M L {set I [lindex [set S [lsort $L]] [expr [set n [llength $L]]/2]]
expr {$n%2?$I:($I+[lindex $S [expr $n/2-1]])/2.}}

Try it online!

Tcl, 124 bytes
proc M L {set n [llength [set S [lsort $L]]]
set I [lindex $S [expr $n/2]]
expr {$n%2?$I:($I+[lindex $S [expr $n/2-1]])/2.}}

Try it online!

Tcl, 133 bytes
proc M L {proc G L\ i {lindex $L [expr $i]}
expr {[set n [llength [set S [lsort $L]]]]%2?[G $S $n/2]:([G $S $n/2]+[G $S $n/2-1])/2.}}

Try it online!

Tcl, 135 bytes
proc M L {expr {[set n [llength [set S [lsort $L]]]]%2?[lindex $S [expr $n/2]]:([lindex $S [expr $n/2]]+[lindex $S [expr $n/2-1]])/2.}}

Try it online!
Still very ungolfed, my first minimum viable product!

Save some bytes with recursive version (translate from my python3 version) -6 bytes

@david Meanwhile you posted, I was outgolfing myself. I tried to golf your suggestion a little more as https://tio.run/##jU/LCoMwELz7FXPw0FJqffYB/QT9gpCDaGqFNEqMIIR8u91QCr2UdmHY2dmdZdc0cl1HPTSoIGH7G5iUQnXmDjYJQxqT06ANQsk5v2awWphZKzCxjBobJnvVioXaiPnuoxJ8e0gj7oL3fEWbdK064bsJhGr3CedulY96RAkb2AQpMuQocMQJZ1yc13LSUs@iAr@wpxT7oCoj5H/6vnpf9xDLXOBgx9lM/pOwpMOf , but I've already shortened my code more than it. Thanks anyway

OK right! Your code is great, I propose you to save still some : 118 bytes

and even more (-2) in removing an unuseful pair of final braces!

Could not grasp how do you distinguish the odd from the even case. Are you doing the average with self in the last line for the odd case?

OK whatever oddity, indices are $a and end-$a.
But I noticed an error in the lsort command e.g. Tcl, by default, sorts 3 5 8 10 in 10 3 5 8 so I added -r option. See the code below
119 bytes

@david lsort does its ordering alphabetically by default

Yeah I meant this is an error in the usage of the command, not in the command itself :)

@david based on you comments and your approach I could golf it down very much.Thanks again!

you're welcome But you still have an issue with sorting, if you add 10 in the first test list, the median returned is false.... -r option !

Failed outgolf: 106 bytes https://tio.run/##jVDLCoMwELz7FXPw0FLUNmof/6BXL2kORUMVUhVNISD59nSj59IuDDs77LAPXSvnxmmoUaLAsrIKxR0Gi@r6RhpwNQ@TRlgIhMYG0owTdrwiAXyWGi34qnGlZP/Ure9MmBDisDXJvonCVuwTFlunXo/RDwqWExhSZMhxxgVX3KzXMtKYZ3GOX4goHX1QlRKyP31fvds@xFIbWHrGW8/gpb/Hug8

@david fixed now!

Arn, 13 12 bytes
Version: 1.1.5
Iõå)n├┼U■¨Mõ

Explained
Unpacked: z&:}+\$.:<:_&:-
z&               Zip array with itself, bind to the following
  :_             Flatten
    :<           Sort ascending
      $.         Split in half
        :}+\     Fold with `:}+`.
            &:-  Bind the half symbol to the expression

How :}+\ works: Takes the last element of the first array and adds to the second array, which is casted to the first element of that array automatically (finally, that feature actually is useful!).
Where a symbol needs to take a value but none is provided, _ is inserted, the implied variable. Ungolfed this looks like
( _ z _ ) & ( :}+\ ( $. ( :< ( _ :_ ) ) ) ) & ( :- _ )

Arn, the boring way, 3 bytes
med

Built in function, can't be compressed.

Pip, 16 bytes
SN:g(CHg+Rgoi)/2

Try It Online!
Explanation
SN:g(CHg+Rgoi)/2
   g              List of command-line arguments
SN:               Sort it (using numeric comparison) in-place
       g          Take that sorted list
        +         Add it (element-wise) with
         Rg       Its reverse
     CH           Chop into two halves (if odd length, second half is longer)
    (      oi)    Select the item at index 0 of the sublist at index 1 (o=1, i=0)
              /2  Divide it by 2

Thunno 2, 1 byte
ṁ

Attempt This Online!
Built-in.
Thunno 2, 11 bytes
l⁻½çṃN$Ṡsim

Attempt This Online!
Non built-in.
Explanation
l⁻½çṃN$Ṡsim  # Implicit input
l⁻           # Length of input, decremented
  ½          # Halve this number
   ç         # Parallelly apply:
    ṃ        #  Ceiling
     N       #  Floor
      $Ṡ     # Input list sorted
        si   # Index into this list
          m  # Mean of this list
             # Implicit output

Python 3.8 (pre-release), 49 44 bytes
-5 Inspired by Luis Mendos Octave answer.
lambda x:sum(sorted(x+x)[(n:=~len(x)):-n])/2

Try it online!

You can remove the space after the or and the parentheses around n:=len(x)//2

Thanks! Removing the parentheses gives syntax error.

@Hunaphu it works in newer versions of Python: Attempt This Online (with Python 3.10)

APL(NARS), 31 chars, 62 bytes
{2÷⍨x[⌊k]+(⌈k←2÷⍨1+≢⍵)⌷x←⍵[⍋⍵]}

test
  t←{2÷⍨x[⌊k]+(⌈k←2÷⍨1+≢⍵)⌷x←⍵[⍋⍵]}
  t 5 4 3 2 1
3
  t 4 3 2 1
2.5
  t 5 40 30 2 1
5
  t 5 40 30 2
17.5
  35÷2
17.5
   t ,80
80
  t 9 3 4 8 7 6
6.5

BQN, 20 bytes
{2÷˜(≠)⊑»+˝˘2↕2/∧}

Try it!

Factor, 6 bytes
median

Try it online!

Pyt, 1 byte
Ṁ

Try it online!
Gotta love built-ins

Thunno, \$ 2 \log_{256}(96) \approx \$ 1.65 bytes
Aa

Attempt This Online!
Built-ins FTW!

JavaScript, 63 bytes
a=>(l=a.sort((k,v)=>k-v).length/2,l*2%2?a[l|0]:(a[l]+a[l-1])/2)

Try it online!

Nekomata, 8 bytes
,o;↔ᶻÐlµ

Attempt This Online!
A port of @ბიმო's Husk answer.
,           Join two copies of the input
 o          Sort
  ;         Split into two parts
   ↔        Reverse the second part
    ᶻÐ      Zip the two parts into a list of pairs
      l     Take the last pair
       µ    Take the mean

license: Creative Commons - Attribution Share-Alike - https://creativecommons.org/licenses/by-sa/4.0/

all_licenses: Creative Commons - Attribution Share-Alike - https://creativecommons.org/licenses/by-sa/3.0/


text:
Unpixellate an image
When you resize an image down to a very small size, it looks very blocky when you scale the pixels back up individually.

In extreme cases, as above, you can no longer reconstruct the original image, as too much information has been lost. Your task is to build a program that will imagine what the original, unscaled image might have looked like in extreme cases such as this one, where the picture has been reduced to a simple palette.
Your program will take an uncompressed bitmap image with three 8-bit RGB channels (with maximum dimensions 16 pixels on each side), and output a second image that produces the original image when scaled down using an average filter (equivalent to GIMP's "Linear" option).
The output image should have the same aspect ratio as the original and have an exact multiple of pixels, to make average-filtering easier. It should also be at least 50 times the size of the original image on each dimension.

What's stopping me from upscaling the input image 50 times?

Personally, I like this idea, but my opinion is admittedly not representative of the community. Hopefully this doesn't get closed before I come up with something neat.

@Pavel nothing. But I wouldn't upvote an answer that did that.

@PatrickRoberts I personally think it's ingenious. There are no rules in the post that bar it

I just realized it's a popcon >_>

What is the voting criterion that voters should award their votes by?

@Maltysen I was just assuming creativity of the algorithm for the imagined image. Consider this challenge.

This appears to be "do simple task in a creative way". That makes it likely to be considered too broad.

This question also lacks a validity criterion, and I agree with @trichoplax 's point. Also you did not specify how you get from the high res image to the low res one. Next time please read the tag description and post your challenge in the sandbox  as advised here.

source: Stack Exchange

license: Creative Commons - Attribution Share-Alike - https://creativecommons.org/licenses/by-sa/3.0/

sort: votes