Bu makale, Fibonacci sayılarını kullanarak geliştirilen ve O(n^(4/3)) en kötü durum çalışma zamanına sahip "Fibonacci Sıralaması" adlı ilginç bir sıralama algoritmasını tanıtıyor. Algoritma, adından da anlaşılacağı gibi, elemanları sıralamak için Fibonacci dizisini (1, 1, 2, 3, 5, ...) kullanır. Yazar, bu algoritmanın nasıl çalıştığını, Fibonacci sayılarının ilginç bir bölünebilirlik özelliğini ve bu özelliği kullanarak algoritmanın karmaşıklığını nasıl kanıtladığını açıklıyor. Ayrıca, Donald Knuth'un prestijli ödül çeklerinden birini nasıl kazandığını da paylaşıyor.
Fibonacci Sıralaması, daha genel bir sıralama yöntemi olan Shellsort'un bir örneğidir. Donald L. Shell'in adını taşıyan Shellsort, tüm elemanları tek adımda doğrudan sıralamak yerine, önce dizinin alt dizilerini "k-sıralama" adı verilen bir süreçle sıralar. k-sıralama, dizinin elemanlarını gruplara ayırır ve bu grupları birbirinden bağımsız olarak sıralar. Her grup, belirli bir 'k' (boşluk olarak da adlandırılır) değeriyle her k'inci eleman alınarak oluşturulur. Bu adımın ardından dizi "k-sıralı" hale gelir, yani tüm 'i' değerleri için A[i] <= A[i + k] koşulu sağlanır.
Shellsort'un çalışma prensibinin anahtarı olan büyüleyici bir özellik, Teorem 1 ile açıklanır: "Bir dizi h-sıralı ise ve ardından k-sıralanırsa, h-sıralı kalmaya devam eder." Bu basit ifadenin kanıtı şaşırtıcı derecede karmaşıktır ve Knuth tarafından yapılan resmi bir kanıtın taslağı makalede sunulur. Bu teorem, Shellsort'un etkinliğini ve doğruluğunu garanti eden temel bir yapı taşıdır. Yazarın Knuth ödülünü alması da, Fibonacci sayılarının bu tür sıralama algoritmalarındaki derin matematiksel özelliklerinin önemini vurgulamaktadır.
Fibonacci sayılarını kullanarak geliştirilen yeni bir sıralama algoritması, Shellsort'un temel prensiplerini ve Donald Knuth'un bilgisayar bilimine katkılarını yenilikçi bir bakış açısıyla ele alıyor.