مرتب‌سازی شکیبانه

بازی با یک دسته بر زده شده شروع می‌شود که ${\displaystyle 1,\dots ,n}$

• 1. در ابتدا هیچ کپه‌ای از کارت وجود ندارد و اولین کارت که مقدار دهی و توزیع می‌شود یک کپهٔ جدید به وجود می‌آورد که تنها دارای یک کارت است.
     
  2. هر کارت جدید ممکن است در یکی از دسته‌های (کپه‌های) موجود قرار بگیرد که در هر کدام از این کپه‌ها کارت با مقدار بیشتر در آغاز قرار دارد. بنابراین با افزوده شدن پی در پی کارت‌ها، تعداد کارت‌های آن کپه یا همهٔ دسته‌های موجود افزایش پیدا می‌کند که در نتیجهٔ آن یک دسته جدید شکل می‌گیرد.
     
  3. وقتی که دیگر کارتی وجود ندارد باقی مانده‌ها را بررسی و محاسبه کنید.(پایان بازی)

یک مسئله مهم و اساسی در این بازی به اتمام رساندن آن با کمترین تعداد کپه‌های ممکن است.

آرایه با یک روش مرتب‌سازی به عنوان ورودی مرتب‌سازی داده شده‌است. به این مسئله به دید جمع‌آوری کارت بنگرید که باید با مرتب‌سازی آماری هر عنصر بر اساس نمایه (index) خود مرتب شود.
نکته:

• این بازی از مقدار واقعی کارت‌ها فقط برای مقایسه بین دو کارت استفاده می‌نماید که با این کار ارتباط هر دو عنصر دلخواه از آرایه بررسی می‌شود.
  

حال بازی مرتب‌سازی صبورانه را شبیه‌سازی کنید وهر کارت جدید را در چپ‌ترین کپه با رعایت قانون قرار دهید. در هر مرحله از این بازی با این استراتژی برچسب‌های (label) کارت‌های سر (top) از چپ به راست به‌طور صعودی هستند. حال توالی مرتب شده را بازیابی کنید و کارت با کمترین مقدار از سر ستون در هر مرحله جمع‌آوری کنید.

اگر تعداد کارت‌ها در محدودهٔ ${\displaystyle 1,\dots ,n}$

ابتدا الگوریتم مرتب‌سازی که در بالا توضیح داده شد را اجرا کنید. در نتیجه آن تعداد اعداد بدست آمده برای هر کپه دارای طول‌های مساوی در بزرگترین زیر دنباله صعودی دارد. هر وقت که یک کارت در سر(top) یک کپه قرار می‌گیرد یک پوینتر به عقب (برگشتی) به کارت سر در کپهٔ قبلی نگه دارید (مثلاً فرض کنید یک عدد با مقداری کمتر از کارت جدید داشته باشیم). در آخر با توجه به اشاره گر به عقب از کارت سر آخرین کپه می‌توانیم یک زیر دنباله نزولی از بزرگترین طول‌ها بازیابی کنیم؛ که در این روش یک حالت بازگشت دارد که جوابی برای الگوریتم بزرگترین زیر دنباله صعودی است.

با توجه به گفته یD. Aldous and P. Diaconis مرتب‌سازی صبورانه اولین الگوریتم بود برای محاسبه بزرگترین زیر دنباله صعودی که توسط Hammersley پیاده‌سازی شده‌است و به وسیلهٔ A.S.C. Ross وBob Floyd مقدمات الگوریتم پیاده‌سازی شد.