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 =) -- http://mail.python.org/mailman/listinfo/python-list
