
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


F patience_sort(&arr)
   I arr.len < 2 {R}
 
   [[T(arr[0])]] piles
   L(el) arr
      L(&pile) piles
         I pile.last > el
            pile.append(el)
            L.break
      L.was_no_break
         piles.append([el])
 
   L(i) 0 .< arr.len
      V min = piles[0].last
      V minPileIndex = 0
      L(j) 1 .< piles.len
         I piles[j].last < min
            min = piles[j].last
            minPileIndex = j
      arr[i] = min
      V& minPile = piles[minPileIndex]
      minPile.pop()
      I minPile.empty
         piles.pop(minPileIndex)
 
V iArr = [4, 65, 2, -31, 0, 99, 83, 782, 1]
patience_sort(&iArr)
print(iArr)
 
V cArr = [‘n’, ‘o’, ‘n’, ‘z’, ‘e’, ‘r’, ‘o’, ‘s’, ‘u’, ‘m’]
patience_sort(&cArr)
print(cArr)
 
V sArr = [‘dog’, ‘cow’, ‘cat’, ‘ape’, ‘ant’, ‘man’, ‘pig’, ‘ass’, ‘gnu’]
patience_sort(&sArr)
print(sArr)