# Algorithm Implementation/Sorting/Patience sort

## C++

Given a generic STL-style input iterator to a sequence, we shall call its elements' value type `card_type`, and assume that we have some container of cards `PileType` (an example could be `vector<card_type>`), and a container of piles `TableType` (which, again, could be just a vector of piles).

In this case, one can define the patience sorting as follows:

```    /**
* Patience sort algorithm as per Aldous and Diaconis,
* using binary search to select the leftmost heap for a new card.
* Compares cards using operator<
*
* TableType requirements
*  -# whatever lower_bound needs
*  -# begin(), end(): ForwardIterator of piles
*
* PileType requirements
*  -# default constructible
*  -# constructible from a single card const reference
*      typedef typename PileType::value_type card_type;
*  -# push_back(const card_type&)
*  -# assignable, lightweight on a singleton pile
*  -# whatever lower_bound needs
*  -# back() implemented or an appropriate pile_less specialization
*/
template < typename PileType, typename TableType, typename InputIterator >
void patience_sort(TableType& table, InputIterator first, InputIterator last) {
typedef PileType pile_type;
typedef typename PileType::value_type card_type;
typedef TableType table_type;
typedef typename table_type::iterator iterator;

while (first != last) {
pile_type new_pile(*first); // read *first only once! (input iterator)
// find the leftmost heap with the top card greater
// than *first , to push *first on it
iterator pile_p = std::lower_bound(
table.begin(), table.end(), new_pile,
pile_less<pile_type>() );
if (pile_p != table.end()) {
pile_p->push_back(new_pile.back());
}
// ...or allocate a new heap on the right with *first
else {
table.push_back(new_pile);
}
first++;
}
}
```

For the std::lower_bound algorithm to work, a tiny utility comparator functor is needed:

```  /**
* Comparator for two piles according to their top card values.
* Compares cards using operator<
*/
template < typename pile_type >
struct pile_less : std::binary_function<pile_type, pile_type, bool>
{
bool operator()(const pile_type& x, const pile_type& y) const
{
return x.back() < y.back();
}
};
/**
* When the algorithm is run with the sole purpose to discover the length of the longest increasing subsequence,
* one doesn't need to store any cards in the piles beneath the topmost one, since only the topmost card's value
* is ever used by the algorithm above, and the length of the longest increasing subsequence is equal to the number of piles on the
* table,
* i.e., ''table.size()'':
*/
/**
* A class representing a pile that is sticky, i.e., once a card
* is put onto its top, it's glued forever. This way, only
* the top card is actually remembered (O(1) memory per heap).
* Used by longest_increasing_subsequence().
*
* Unfortunately, such heap is impossible to use in more advanced
* algorithms, such as the Bespamyatnykh and Segal one, for the
* actual longest increasing subsequence recovery.
*/
template< typename Card >
struct StickyPile { // cards stick together when put here :-)
typedef Card value_type;
typedef const value_type& const_reference;
StickyPile(const Card& _card) : card(_card) {}
void push_back(const Card& _card) { card = _card; }
const_reference back() const { return card; }
private:
Card card;
};

/** Find the length of the longest increasing subsequence
* given by the given iterator range, using patience_sort().
* Compares cards using operator<
*/
template< typename InputIterator >
size_t longest_increasing_subsequence(
InputIterator first, InputIterator last)
{
typedef typename std::iterator_traits<InputIterator>::value_type Card;
typedef StickyPile<Card> pile_type;
typedef std::vector< pile_type > table_type;
table_type table;
patience_sort<pile_type>(table, first, last);
return table.size();
}

/* The above GPL code is based on excerpts from [[http://www.tarunz.org/~vassilii/pub/c++/patience_sort.hpp patience_sort.hpp]],
which also provides versions of the same functionality parametrized by any given comparator (rather than using operator< ). */
```

## 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
}
System.out.println("longest increasing subsequence has length = " + piles.size());

// 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()); }
}
}
```

## Python

```import bisect, heapq

def sort(seq):
piles = []
for x in seq:
new_pile = [x]
i = bisect.bisect_left(piles, new_pile)
if i != len(piles):
piles[i].insert(0, x)
else:
piles.append(new_pile)
print "longest increasing subsequence has length =", len(piles)

# priority queue allows us to retrieve least pile efficiently
for i in xrange(len(seq)):
small_pile = piles[0]
seq[i] = small_pile.pop(0)
if small_pile:
heapq.heapreplace(piles, small_pile)
else:
heapq.heappop(piles)
assert not piles

foo = [4, 65, 2, 4, -31, 0, 99, 1, 83, 782, 1]
sort(foo)
print foo
```