I found a sort I find quite impressive. It claims to be (n^2)!. While I haven't tried to verify the math, I doubt my attempts would be better than the authors, I did try running this search to sort the recommended max of seven integers. Just posting for the interest of others.
More on it here:
http://richardhartersworld.com/cri_d/cri/2001/badsort.html#evilsort
I thought your post said O(n^2) ! (with an exclamation mark) at first. When I realized it was a factorial I burst out laughing. The author writes:
ReplyDelete"On my system, testing with 7 took about 24 seconds.
If my calculation that the process is Omega((n ^ 2)!) is
accurate, and that is the dominating factor at size 7,
sorting 8 elements would take far longer than my
lifetime. Far longer than the sun's lifetime.
Probably far longer than the universe's lifetime."
Hilarious!