/prog/ challenge: sorting algorithm

It's been a long time since the last /prog/ challenge. However, since then the board has filled up with stupid assignments and the return of FrozenVoid.

To level the challenge with current times, here's the proposal:

Design and implement a sorting algorithm with complexity O(nⁿ). Lower complexities will not be allowed. Redundand or blatantly no-ops will not be allowed. Poster must provide proof of complexity.

Extra points will be awarded for a O(nⁿⁿ) or for an INTERCAL implementation.

Deadline is yesterday. Good luck.

>>15
Actually, bogosort is O(infinite), since that's the worst case scenario and the average of it (with 1 as best) is still infinite ((infinite + 1) / 2 = infinite).