
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


Sort an array of numbers (of any convenient size) into ascending order using   Patience sorting.



Related task

   Longest increasing subsequence


with javascript_semantics

function patience_sort(sequence s)
    -- create list of sorted lists
    sequence piles = {}
    for i=1 to length(s) do
        object n = s[i]
        for p=1 to length(piles)+1 do
            if p>length(piles) then
                piles = append(piles,{n})
            elsif n>=piles[p][$] then
                piles[p] = append(deep_copy(piles[p]),n)
                exit
            end if
        end for
    end for
    -- merge sort the piles
    sequence res = ""
    while length(piles) do
        integer idx = smallest(piles,return_index:=true)
        res = append(res,piles[idx][1])
        if length(piles[idx])=1 then
            piles[idx..idx] = {}
        else
            piles[idx] = piles[idx][2..$]
        end if
    end while
    return res
end function
 
constant tests = {{4,65,2,-31,0,99,83,782,1},
                  {0,8,4,12,2,10,6,14,1,9,5,13,3,11,7,15},
                  "nonzerosum",
                  {"dog", "cow", "cat", "ape", "ant", "man", "pig", "ass", "gnu"}}
 
for i=1 to length(tests) do
    pp(patience_sort(tests[i]),{pp_IntCh,false})
end for
