
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



def swap(container, ixA, ixB) {
    def temp := container[ixA]
    container[ixA] := container[ixB]
    container[ixB] := temp
}
 
/** Reverse order of elements of 'sequence' whose indexes are in the interval [ixLow, ixHigh] */
def reverseRange(sequence, var ixLow, var ixHigh) {
    while (ixLow < ixHigh) {
        swap(sequence, ixLow, ixHigh)
        ixLow += 1
        ixHigh -= 1
    }
}
 
/** Algorithm from <http://marknelson.us/2002/03/01/next-permutation>, allegedly from a version of the C++ STL */
def nextPermutation(sequence) {
    def last := sequence.size() - 1
    var i := last
    while (true) {
        var ii := i
        i -= 1
        if (sequence[i] < sequence[ii]) {
            var j := last + 1
            while (!(sequence[i] < sequence[j -= 1])) {} # buried side effect
            swap(sequence, i, j)
            reverseRange(sequence, ii, last)
            return true
        }
        if (i == 0) {
            reverseRange(sequence, 0, last)
            return false
        }
    }
}
 
/** Note: Worst case on sorted list */
def permutationSort(flexList) {
    while (nextPermutation(flexList)) {}
}