A classic sorting code-golf question This is a code-golf question.

Input

A list of non-negative integers in whatever format is the most convenient.

Output

The same list in sorted order in  whatever format is the most convenient.

Restriction


Your code must run in O(n log n) time in the worst case where nis the number of integers in the input. This means that randomized quicksort is out for example.  However there are many many other options to choose from.
Don't use any sorting library/function/similar.  Also don't use anything that does most of the sorting work for you like a heap library. Basically, whatever you implement, implement it from scratch.


You can define a function if you like but then please show an example of it in a full program actually working.  It should run successfully and quickly on all the test cases below.

Test cases

In: [9, 8, 3, 2, 4, 6, 5, 1, 7, 0]
Out:[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

In: [72, 59, 95, 68, 84]
Out:[59, 68, 72, 84, 95]

In: [2, 2, 1, 9, 3, 7, 4, 1, 6, 7]
Out:[1, 1, 2, 2, 3, 4, 6, 7, 7, 9]

In: [2397725, 1925225, 3304534, 7806949, 4487711, 8337622, 2276714, 3088926, 4274324,  667269]
Out:[667269,1925225, 2276714, 2397725,3088926, 3304534, 4274324, 4487711, 7806949, 8337622]


Your answers

Please state the sorting algorithm you have implemented and the length of your solution in the title of your answer.

O(n log n) time sorting algorithms

There are many O(n log n) time algorithms in existence. This table has a list of some of them.
Haskell, 87 80 89
s%[]=s
(x:a)%q|x&lt;=q!!0=x:a%q
p%q=q%p
j(x:y:s)=x%y:j s
j a=a
r[x]=x
r s=r$j s
s=r.map(:[])

This is merge sort, implemented from the bottom up.
first we package every element into it's own list, and then merge them two-by-two, and again merge them two-by-two, until we're left with one list.
(%) is the merge function 
j merges pairs in a list of lists 
r merges a complete list of lists 
s is the sorting function. 
Usage:
Run an interpreter, and enter s [3,5,2,6,7].
Edit:
the way I was merging things before wasn't the right order, So to fix it I needed 9 more characters.