/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.

Is there an algorithm that only sorts the output when time goes to infinity, so the sequences generated are only converging to the sorted sequence, or is that impossible given finite input?