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 the longest increasing subsequence in a given array.
Facts
Time Complexity
Time Complexity (category)Linearithmic Time -- O(n log n) 1 Classification
Design Technique Connections
In Field
Source Patience Sorting (Wikipedia)
Uses Design Technique
Sources
1. Patience Sorting (Wikipedia)
Article text
The first phase of patience sort, the card game simulation, can be implemented to take O(n log n) comparisons in the worst case for an n-element input array: there will be at most n piles, and by construction, the top cards of the piles form an increasing sequence from left to right, so the desired pile can be found by binary search.
Wikipedia infobox: time complexity linearithmic
linearithmic
In Field: Algorithms and Complexity Theory, Lead sentence
patience sorting is a sorting algorithm inspired by, and named after, the card game patience.
In Group: Comparison Sorting Algorithms, Lead
In computer science, patience sorting is a sorting algorithm inspired by, and named after, the card game patience.
View the SourceReader Challenges (0)
No disputes yet. Spotted an error or a better source? Open the first one.
Sign in to dispute this or suggest a correction.