
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


module PatienceSortFn (Ord : Set.OrderedType) : sig
    val patience_sort : Ord.t list -> Ord.t list
  end = struct
 
  module PilesSet = Set.Make
    (struct
       type t = Ord.t list
       let compare x y = Ord.compare (List.hd x) (List.hd y)
     end);;
 
  let sort_into_piles list =
    let piles = Array.make (List.length list) [] in
    let bsearch_piles x len =
      let rec aux lo hi =
        if lo > hi then
          lo
        else
          let mid = (lo + hi) / 2 in
          if Ord.compare (List.hd piles.(mid)) x < 0 then
            aux (mid+1) hi
          else
            aux lo (mid-1)
      in
        aux 0 (len-1)
    in
    let f len x =
      let i = bsearch_piles x len in
      piles.(i) <- x :: piles.(i);
      if i = len then len+1 else len
    in
    let len = List.fold_left f 0 list in
    Array.sub piles 0 len
 
  let merge_piles piles =
    let pq = Array.fold_right PilesSet.add piles PilesSet.empty in
    let rec f pq acc =
      if PilesSet.is_empty pq then
        acc
      else
        let elt = PilesSet.min_elt pq in
        match elt with
          [] -> failwith "Impossible"
        | x::xs ->
          let pq' = PilesSet.remove elt pq in
          f (if xs = [] then pq' else PilesSet.add xs pq') (x::acc)
    in
    List.rev (f pq [])
 
  let patience_sort n =
    merge_piles (sort_into_piles n)
end