O(n log n) zamanda bütün en uzun artan altdizileri bulur.
Sabır sıralaması bilgisayar bilimlerinde kullanılan ve bir kâğıt oyununa
dayanan bir sıralama algoritmasıdır.
Kağıt oyunu
Oyun, 1, 2, ..., n biçiminde numaralandırılmış n adet
oyun kağıdından oluşan desteyle oynanır. Kağıtlar masanın üzerinde aşadaki kurallara
uygun olarak bölümlere ayrılır:
- Başlangıçta hiçbir kâğıt yığını yoktur. Oynana ilk kart tek kartta oluşan bir alt
deste oluşturur.
- Oynanan her yeni kart ya en üstte kendisinden daha büyük bir kart bulunan kâğıt
yığının en üstüne ya da masadaki tüm yığınların en sağına yeni bir yığın oluşturmak
üzere yerleştirilir.
- Dağıtılacak kâğıt kalmadığı zaman oyun biter
Oyunun amacı oyunu olabilecek en az sayıda kâğıt yığınıyla bitirmektir.
