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

(defun same (list1 list2)
  (or (and (null list1) (null list2))
      (let ((item (car list1)))
        (and (= (count item list1) (count item list2))
             (same (remove item list1) (remove item list2))))))

(defun n^n-sort (list)
  (let ((length (length list))
        (new-list nil))
    (dotimes (i length)
      (push (elt list (random length)) new-list))
    (if (and (same list new-list) (apply #'<= new-list))
        new-list
        (n^n-sort list))))

It's similar to Bogosort, except that instead of just shuffling the list, it takes random items without making sure that it gets each one and only gets each one once. So, for the same reason that Bogosort is O(n!) (it has a 1/n! chance of getting the list right) mine is O(n^n). Technically it's a little less if there are duplicates in the input list, though.