Tim Peters adlı bir yazılımcı 2002 yılında Timsort adında bir melez sıralama algoritması geliştirdi. Bu algoritma merge sort(birleştirmeli sıralama) ve insertion sort(eklemeli sıralama) algoritmalarının akıllıca birleşiminden oluşan, gerçek hayat uygulamalarında çok güçlü bir algoritmaydı.

Timsort öncelikle Python için tasarlandı fakat daha sonra Java Collections tasarımcısı olan Joshua Bloch tarafından Java’ya da port edildi(Şu anda java.util.Collections.sort ve java.util.Arrays.sort’un altında bulunuyor). Timsort şu anda ise Android SDK’da, Sun JDK’da ve OpenSDK’da varsayılan sıralama algoritması olarak kullanılıyor. Bu platformların popülerliği göze alacak olursak, Timsort algoritmasının milyonlarca cihazda kullanıldığını söylemek yanlış olmaz.

2015 yılına geri döndüğümüzde, bazı yazılımcılar çok yaygın olarak kullanılan Timsort algoritması üzerinde bazı testler uygulamaya başladılar. Maalesef algoritmanın doğruluğunu kanıtlamakta başarısızlığa uğradılar. Yakın bir analizde algoritmanın teorik olarak hatalı olduğunu fark ettiler ve bu da onları bug’ı bulmaya yönlendirdi(Ki şu anda Python’da bu hatayı görebilmek mümkün).

Android, Java ve Python’da bulunan bug

Peki buradaki bug nedir? Neden kendiniz bug’ı üretmiyorsunuz?

Java’da Timsort bugını üretmek:

git clone https://github.com/abstools/java-timsort-bug.git
cd java-timsort-bug
javac *.java
java TestTimSort 67108864
Beklenen çıktı:
Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: 40
at java.util.TimSort.pushRun(TimSort.java:413)
at java.util.TimSort.sort(TimSort.java:240)
at java.util.Arrays.sort(Arrays.java:1438)
at TestTimSort.main(TestTimSort.java:18)
Gidiş yolu:

Timsort Algoritması Prensipte Nasıl Çalışır?

Yukarıda da bahsettiğimiz gibi Timsort insertion sort ve merge sort algoritmalarının birleşiminden oluşan bir melez sıralama algoritmasıdır.

Algoritma, giriş dizisini soldan sağa doğru ardışık sıralı segmentleri(terimse olarak run deniyor.) düzenlemek üzerine kuruludur. Eğer segment çok kısa ise, insertion sort ile genişletiliyor. Oluşturulan segmentlerin uzunlukları da runLen adı verilen bir diziye ekleniyor. Ne zaman runLen dizisine yeni bir segment eklenecek olursa, mergeCollapse adlı fonksiyon, runLen’de bulunan son 3 element aşağıdaki iki koşulu sağlayana kadar segmentleri birleştiriyor.

  1. runLen [n-2] > runLen [n-1] + runLen [n]
  2. runLen [n-1] > runLen [n]

Buradaki “n” son eklenen segmentin index numarasını temsil ediyor. En sonunda ise tüm segmentler birleştirilerek giriş dizisinin sıralanmış hali teslim ediliyor.

Performans nedenlerinden ötürü, runLen’e tahsis edilen belleğin mümkün olan en az değerde, fakat yine de tüm segmentleri depolayabilecek kapasitede olması çok önemlidir.

Timsort Bug’ı için Gidiş Yolu

Aşağıdaki kod parçası, son 3 segment için denklemleri kontrol eden mergeCollapse’ı gösteriyor.

private void mergeCollapse() {
  while (stackSize > 1) {
    int n = stackSize - 2;
    if (n > 0 && runLen[n-1] <= runLen[n] + runLen[n+1]) {
      if (runLen[n - 1] < runLen[n + 1])
         n--;
      mergeAt(n);
    } else if (runLen[n] <= runLen[n + 1]) {
      mergeAt(n);
    } else {
      break; // denklem sağlandı.
    }
  }
}

Ne yazıkki, bu tüm segmentlerin denklemleri sağlayıp sağlayamadığını söylemekte yetersiz kalıyor. runLen’de aşağıdaki gibi bir içeriğin olduğunu farz edelim(n = 4):

120, 80, 25, 20, 30

İlk döngü yinelemesinde, 20 ile 25 birleşiyor(25 < 20 + 30 ve 20 < 30 olmasından dolayı).

120, 80, 45, 30

Döngünün 2. dönüşünde(Şu anda n = 3), son 3 değerin 80 > 45 + 30 ve 45 > 30 olduğundan dolayı denklemleri gerçekleştirdiğini görüyoruz. Fakat mergeCollapse, tamamiyle denklemleri sağlayan bir çıktı vermiş gibi gözükmüyor(Çünkü 120 < 80 + 45).

Python ve Android/Java İçin Tavsiye Edilen Çözümler

Bug hakkındaki analizler Java Bug Tracker‘a iletilmiş ve kabul edilmiş durumda. Bug şu anda Java’nin Android versiyonunda, OpenJDK ve OracleJDK versiyonlarında mevcut, ki tüm bu üçü TimSort’un aynı source kodunu kullanmaktalar. Buna ek olarak, bug şu anda Python’da da gözlenmekte. Alttaki başlıklarda bu bugları ve çözümlerini ayrı ayrı ele alacağız. Üstteki yazılarda da bahsettiğimiz üzere aslında sorunun çözümü oldukça basit. runLen’deki son 3 segment için denklemleri kontrol etmek yerine, son 4 eleman için kontrol etmemiz gerekiyor.

Python’daki hatalı olan merge_collapse fonksiyonu

Python için TimSort(Python API ile birlikte C de yazılmıştır.) mercurial repository’sinde mevcut. Algoritması da şurada açıklanmış.

TimSort’un Java versiyonu aslen CPython versiyonundan port edilmiştir. Bu versiyon bug’ı içermekle birlikte en fazla 2^64 eleman ile çalışmak için tasarlanmıştır. Neyse ki şu anda, makinelerde 2^64 byte kadar bellek kullan bilgisayar olmadığı için bu bizim için bir sorun teşkil etmiyor. Şuanki en güçlü süper bilgisayarın bile 2^50 byte kadarlık bir bellek ayırabildiğini düşünürsek uzun süre de bir sıkıntı olmayacakmış gibi duruyor.

/* The maximum number of entries in a MergeState's
 * pending-runs stack.
 * This is enough to sort arrays of size up to about
 *     32 * phi ** MAX_MERGE_PENDING
 * where phi ~= 1.618.  85 is ridiculously large enough, 
 * good for an array with 2**64 elements.
 */
# define MAX_MERGE_PENDING 85

merge_collapse(MergeState *ms)
{
    struct s_slice *p = ms->pending;

    assert(ms);
    while (ms->n > 1) {
        Py_ssize_t n = ms->n - 2;
        if (n > 0 && p[n-1].len <= p[n].len + p[n+1].len) {
            if (p[n-1].len < p[n+1].len)
                --n;
            if (merge_at(ms, n) < 0)
                return -1;
        }
        else if (p[n].len <= p[n+1].len) {
                 if (merge_at(ms, n) < 0)
                        return -1;
        }
        else
            break;
    }
    return 0;
}

Python için düzeltilmiş merge_collapse fonksiyonu

merge_collapse(MergeState *ms)
{
    struct s_slice *p = ms->pending;

    assert(ms);
    while (ms->n > 1) {
        Py_ssize_t n = ms->n - 2;
        if (     n > 0   && p[n-1].len <= p[n].len + p[n+1].len
            || (n-1 > 0 &&  p[n-2].len <= p[n].len + p[n-1].len)) {
            if (p[n-1].len < p[n+1].len)
                --n;
            if (merge_at(ms, n) < 0)
                return -1;
        }
        else if (p[n].len <= p[n+1].len) {
                 if (merge_at(ms, n) < 0)
                        return -1;
        }
        else
            break;
    }
    return 0;
}

Java/Android’de bulunan hatalı merge_collapse fonksiyonu

Üstte Python’da bahsettiğimiz hatanın aynısı.

 private void mergeCollapse() {
        while (stackSize > 1) {
            int n = stackSize - 2;
            if (n > 0 && runLen[n-1] <= runLen[n] + runLen[n+1]) {
                if (runLen[n - 1] < runLen[n + 1])
                    n--;
                mergeAt(n);
            } else if (runLen[n] <= runLen[n + 1]) {
                mergeAt(n);
            } else {
                break; // Denklemler sağlandı.
            }
        }
    }

Java/Android için düzeltilmiş merge_collapse fonksiyonu

Yine Python’daki hatanın çözümüyle eşdeğer bir çözüm.

private void newMergeCollapse() {
     while (stackSize > 1) {
       int n = stackSize - 2;
       if (   (n >= 1 && runLen[n-1] <= runLen[n] + runLen[n+1])
           || (n >= 2 && runLen[n-2] <= runLen[n] + runLen[n-1])) {
                if (runLen[n - 1] < runLen[n + 1])
                    n--;
            } else if (runLen[n] > runLen[n + 1]) {
                break; // Denklemler sağlandı.
            }
            mergeAt(n);
        }
    }