stable algorithm with complexity O(n)

[cmdrrickhunter@yaho.com]

Just because its such an interesting problem, I'll take a stab at it.

It can be proven that you cannot sort an arbitrarily large set of
numbers, given no extra information, faster than O(n log n).  It is
provable using information theory.  However, if your teacher is giving
you evil problems, there's no reason you can't be evil in return:

Evil trick 1:  Allocate an array of n^2 booleans, initialized to false
(This is O(n^2)).  Declare this to be "before the sort"  Then iterate
through the list and set each matching entry in the array to True
(This is O(n)).  Now you have them "sorted."  To get access to the
data, you need to iterate across the array O(n^2), but this is "after
the sort"

Evil trick 2: inserting into a set is O(1), so you could insert n
items into a set.  This is O(n).  Then you can argue that, since the
set cares not about order, it is as good as ordered!

Evil trick 3: pull up your python debugger, and have your program
search for the right answer in your teacher's test library.  If done
smart, this could even be an O(1) sort O_o  (queue Nukees reference:
"Welcome to my computer security course.  Your grades have already
been entered into the school's grading systems as Fs.  You have one
semester to change that, good luck")

... these are fun =)