Patience sorting
Sorting algorithm
>
In computer science, patience sorting is a sorting algorithm inspired by, and named after, the card game patience. A variant of the algorithm efficiently computes the length of a longest increasing subsequence in a given array. Wikipedia
Worst-case complexity: n*log(n)
Best-case performance: O(n); occurs when the input is pre-sorted
Worst-case performance: O(n log n)