Некорректная работа функции сортировки в Android, Java и Python

Рекомендуем почитать:

Хакер #306. OAuth от и до

• Содержание выпуска
• Подписка на «Хакер»-60%

В 2002 году Тим Петерс разработал гибридный алгоритм сортировки Timsort, который хитроумно сочетает в себе сортировку вставками и сортировку слиянием. Сейчас это стандартный алгоритм сортировки в Python, OpenJDK, Sun JDK в Android JDK. К сожалению, недавно в нём обнаружен явный баг. Учитывая популярность вышеупомянутых платформ, речь идёт о миллиардах компьютеров и мобильных устройств.

Специалисты из консорциума Envisage провели анализ, как работают реализации Timsort в Java и Python. Ониубедились, что в обоих случаях возможен выход за пределы массива.

Более подробное исследование позволило найти конкретный баг в реализациях TimSort. Этот баг содержится в коде, который отвечает за слияние подмассивов. В Java/Android он выглядит так.

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; // Invariant is established
    }
  }
}

Согласно алгоритму, слияние подмассивов происходит до тех пор, пока не достигается выполнение двух правил:

X > Y + Z
Y > Z

Так вот, при некоторых значениях вышеприведённый код mergeCollapse приводит к ошибке. Например, если взять такие значения runLen.

120, 80, 25, 20, 30

После первой итерации цикла происходит слияние 25 и 20 (поскольку 25 < 20 + 30 и 25 < 30).

120, 80, 45, 30

После второй итерации программа прекращает работу, потому что результат удовлетворяет поставленным условиям (80 > 45 + 30 и 45 > 30). Но на самом деле 120 < 80 + 45, а проверка этого условия не предусмотрена кодом, что и приводит к ошибке.

Функцию в Java/Android следует исправить следующим образом.

 private void newMergeCollapse() {
     while (stackSize > 1) {
       int n = stackSize - 2;
       if ( n > 0 && runLen[n-1]  0 && runLen[n-2] <= runLen[n] + runLen[n-1]) {
                if (runLen[n - 1] < runLen[n + 1])
                    n--;
            } else if (n runLen[n + 1]) {
                break; // Invariant is established
            }
            mergeAt(n);
        }
    }

На видео показано, как вызывается exception.

Подробное описание бага содержится в научной статье. На сайте Envisage выложен генератор тестов TestTimSort.java, который «ломает» TimSort, а также исходный код генератора.