Sıralama algoritması
Öğeleri bir karşılaştırma kuralına göre dizen yöntem; bilgisayar biliminin en kapsamlı incelenmiş problemi.
Karşılaştırmaya dayalı sıralama ispatlanabilir biçimde O(n log n)’i aşamaz: n öğenin n! olası dizilişi vardır ve her karşılaştırma arama uzayını en fazla yarıya indirir. Hızlı sıralama, birleştirmeli sıralama ve yığın sıralaması bu sınıra bellek, kararlılık ve en kötü durum açısından farklı ödünlerle ulaşır. Sayma sıralaması ve taban (radix) sıralaması hiç karşılaştırma yapmayarak sınırı aşar, ama anahtarların bilinen aralıkta tamsayı olmasını gerektirir.
Pratikte kimse kendisi yazmaz. Standart kitaplıklar on yıllardır işlenmiş melezlerle gelir: C++’ta introsort (özyineleme derinleşince yığın sıralamasına geçen hızlı sıralama), Python ve Java’da nesneler için Timsort, Rust’ta örüntü bozucu hızlı sıralama (pdqsort). İlginç soru çoğu zaman hangi algoritma olduğu değil, hangi karşılaştırmanın kullanıldığıdır: metin harmanlaması dile göre değişir ve tutarsız bir karşılaştırıcı yalnızca yanlış sıra değil, tanımsız davranış üretir.