Sorting algorithms/Patience sort

Sort an array of integers (of any convenient size) into ascending order using Patience sorting.

Sorting algorithms/Patience sort is a draft programming task. It is not yet considered ready to be promoted as a complete task, for reasons that should be found in its talk page.

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 log²n) sorts
Shell Sort

O(n²) 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

Java

<lang java>import java.util.*;

public class PatienceSort {

   public static <E extends Comparable<? super E>> void sort (E[] n) {
       List<Pile<E>> piles = new ArrayList<Pile<E>>();
       // sort into piles
       for (E x : n) {
           Pile<E> newPile = new Pile<E>();
           newPile.push(x);
           int i = Collections.binarySearch(piles, newPile);
           if (i < 0) i = ~i;
           if (i != piles.size())
               piles.get(i).push(x);
           else
               piles.add(newPile);
       }

       // priority queue allows us to retrieve least pile efficiently
       PriorityQueue<Pile<E>> heap = new PriorityQueue<Pile<E>>(piles);
       for (int c = 0; c < n.length; c++) {
           Pile<E> smallPile = heap.poll();
           n[c] = smallPile.pop();
           if (!smallPile.isEmpty())
               heap.offer(smallPile);
       }
       assert(heap.isEmpty());
   }

   private static class Pile<E extends Comparable<? super E>> extends Stack<E> implements Comparable<Pile<E>> {
       public int compareTo(Pile<E> y) { return peek().compareTo(y.peek()); }
   }

   public static void main(String[] args) {

Integer[] a = {4, 65, 2, -31, 0, 99, 83, 782, 1}; sort(a); System.out.println(Arrays.toString(a));

   }

}</lang>

Output:

[-31, 0, 1, 2, 4, 65, 83, 99, 782]