Well, spaghetti sort runs in linear time: O(n) time is spent setting up the device, and O(n) reading out the result. The actual sorting step is O(1) !!!

Unfortunately, it's limited to sorting numbers, and uses O(n) additional space (to be precise, it uses O(n) additional volume).