
Sorting Algorithm

This is a sorting algorithm.   It may be applied to a set of data in order to sort it.    
For comparing various sorts, see compare sorts.  
For other sorting algorithms,   see sorting algorithms,   or:

O(n logn) sorts
Heap sort |
Merge sort |
Patience sort |
Quick sort
O(n log2n) sorts
Shell Sort
O(n2) sorts
Bubble sort |
Cocktail sort |
Cocktail sort with shifting bounds |
Comb sort |
Cycle sort |
Gnome sort |
Insertion sort |
Selection sort |
Strand sort
other sorts
Bead sort |
Bogo sort |
Common sorted list |
Composite structures sort |
Custom comparator sort |
Counting sort |
Disjoint sublist sort |
External sort |
Jort sort |
Lexicographical sort |
Natural sorting |
Order by pair comparisons |
Order disjoint list items |
Order two numerical lists |
Object identifier (OID) sort |
Pancake sort |
Quickselect |
Permutation sort |
Radix sort |
Ranking methods |
Remove duplicate elements |
Sleep sort |
Stooge sort |
[Sort letters of a string] |
Three variable sort |
Topological sort |
Tree sort


Task

Implement a permutation sort, which proceeds by generating the possible permutations
of the input array/list until discovering the sorted one.

Pseudocode:

while not InOrder(list) do
    nextPermutation(list)
done



(defun factorial (n)
  (loop for result = 1 then (* i result)
        for i from 2 to n
        finally (return result)))
 
(defun nth-permutation (k sequence)
  (if (zerop (length sequence))
      (coerce () (type-of sequence))
      (let ((seq (etypecase sequence
                   (vector (copy-seq sequence))
                   (sequence (coerce sequence 'vector)))))
        (loop for j from 2 to (length seq)
              do (setq k (truncate (/ k (1- j))))
              do (rotatef (aref seq (mod k j))
                          (aref seq (1- j)))
              finally (return (coerce seq (type-of sequence)))))))
 
(defun sortedp (fn sequence)
  (etypecase sequence
    (list (loop for previous = #1='#:foo then i
                for i in sequence
                always (or (eq previous #1#)
                           (funcall fn i previous))))
    ;; copypasta
    (vector (loop for previous = #1# then i
                  for i across sequence
                  always (or (eq previous #1#)
                             (funcall fn i previous))))))
 
(defun permutation-sort (fn sequence)
  (loop for i below (factorial (length sequence))
        for permutation = (nth-permutation i sequence)
        when (sortedp fn permutation)
          do (return permutation)))