
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


import std/decls
 
func patienceSort[T](a: var openArray[T]) =
 
  if a.len < 2: return
 
  var piles: seq[seq[T]]
 
  for elem in a:
    block processElem:
      for pile in piles.mitems:
        if pile[^1] > elem:
          pile.add(elem)
          break processElem
      piles.add(@[elem])
 
  for i in 0..a.high:
    var min = piles[0][^1]
    var minPileIndex = 0
    for j in 1..piles.high:
      if piles[j][^1] < min:
        min = piles[j][^1]
        minPileIndex = j
 
    a[i] = min
    var minPile {.byAddr.} = piles[minPileIndex]
    minPile.setLen(minpile.len - 1)
    if minPile.len == 0: piles.delete(minPileIndex)
 
 
when isMainModule:
 
  var iArray = [4, 65, 2, -31, 0, 99, 83, 782, 1]
  iArray.patienceSort()
  echo iArray
  var cArray = ['n', 'o', 'n', 'z', 'e', 'r', 'o', 's', 'u','m']
  cArray.patienceSort()
  echo cArray
  var sArray = ["dog", "cow", "cat", "ape", "ant", "man", "pig", "ass", "gnu"]
  sArray.patienceSort()
  echo sArray