
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


#lang racket/base
(require racket/match racket/list)
 
;; the car of a pile is the "bottom", i.e. where we place a card
(define (place-greedily ps-in c <?)
  (let inr ((vr null) (ps ps-in))
    (match ps
      [(list) (reverse (cons (list c) vr))]
      [(list (and psh (list ph _ ...)) pst ...)
       #:when (<? c ph) (append (reverse (cons (cons c psh) vr)) pst)]
      [(list psh pst ...) (inr (cons psh vr) pst)])))
 
(define (patience-sort cs-in <?)
  ;; Scatter
  (define piles
    (let scatter ((cs cs-in) (ps null))
      (match cs [(list) ps] [(cons a d) (scatter d (place-greedily ps a <?))])))
  ;; Gather
  (let gather ((rv null) (ps piles))
    (match ps
      [(list) (reverse rv)]
      [(list psh pst ...)
       (let scan ((least psh) (seens null) (unseens pst))
         (define least-card (car least))
         (match* (unseens least)
           [((list) (list l)) (gather (cons l rv) seens)]
           [((list) (cons l lt)) (gather (cons l rv) (cons lt seens))]
           [((cons (and ush (cons u _)) ust) (cons l _))
            #:when (<? l u) (scan least (cons ush seens) ust)]
           [((cons ush ust) least) (scan ush (cons least seens) ust)]))])))
 
(patience-sort (shuffle (for/list ((_ 10)) (random 7))) <)