C++ Implementation
This is an implementation using Patience Sorting to sort an array, performing O(n log n) time complexity.
#include
#include
#include
#include
template
bool pile_less(const PileType& x, const PileType& y)
{ return x.top < y.top;
}
// reverse less predicate to turn max-heap into min-heap
template
bool pile_more(const PileType& x, const PileType& y)
{ return pile_less(y, x);
}
template
void patience_sort(Iterator begin, Iterator end)
{ typedef typename std::iterator_traits::value_type DataType; typedef std::stack PileType; std::vector piles; for (Iterator it = begin; it != end; it++) { PileType new_pile; new_pile.push(*it); typename std::vector::iterator insert_it = std::lower_bound(piles.begin, piles.end, new_pile, pile_less); if (insert_it == piles.end) piles.push_back(new_pile); else insert_it->push(*it); } // sorted array already satisfies heap property for min-heap for (Iterator it = begin; it != end; it++) { std::pop_heap(piles.begin, piles.end, pile_more); *it = piles.back.top; piles.back.pop; if (piles.back.empty) piles.pop_back; else std::push_heap(piles.begin, piles.end, pile_more); }
}