
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


def patienceSort:
  length as $size
  | if $size < 2 then .
    else
      reduce .[] as $e ( {piles: []};
        .outer = false
	| first( range(0; .piles|length) as $ipile
                 | if .piles[$ipile][-1] < $e
                   then .piles[$ipile] += [$e]
                   | .outer = true
		   else empty
		   end ) // .
        | if (.outer|not) then .piles += [[$e]] else . end )
    | reduce range(0; $size) as $i (.;
        .min = .piles[0][0]
        | .minPileIndex = 0
        | reduce range(1; .piles|length) as $j (.;
            if .piles[$j][0] < .min
            then .min = .piles[$j][0]
            | .minPileIndex = $j
	    else .
	    end )
        | .a += [.min]
	| .minPileIndex as $mpx
	| .piles[$mpx] |= .[1:]
        | if (.piles[$mpx] == []) then .piles |= .[:$mpx] + .[$mpx + 1:]
	  else .
	  end)
  end
  | .a ;
 
 
[4, 65, 2, -31, 0, 99, 83, 782, 1],
 ["n", "o", "n", "z", "e", "r", "o", "s", "u", "m"],
 ["dog", "cow", "cat", "ape", "ant", "man", "pig", "ass", "gnu"]
| patienceSort