A Cost Optimal Parallel Algorithm for Patience Sorting

In this paper, we consider a parallel algorithm for the patience sorting. The problem is not known to be in the class NC or P-complete. We propose two algorithms for the patience sorting of n distinct integers. The first algorithm runs in O(m(n/p+log n))time using p processors on the EREW PRAM, where m is the number of decreasing subsequences in a solution of the patience sorting. The second algorithm runs in O(log n+n log n/p+m2log n/p+m log p)time using p processors on the EREW PRAM. If 1<p