152,60
рейтинг
24 ноября 2011 в 12:46

Разработка → Алгоритм сортировки Timsort

Timsort, в отличии от всяких там «пузырьков» и «вставок», штука относительно новая — изобретен был в 2002 году Тимом Петерсом (в честь него и назван). С тех пор он уже стал стандартным алгоритмом сортировки в Python, OpenJDK 7 и Android JDK 1.5. А чтобы понять почему — достаточно взглянуть на вот эту табличку из Википедии.



Среди, на первый взгляд, огромного выбора в таблице есть всего 7 адекватных алгоритмов (со сложностью O(n logn) в среднем и худшем случае), среди которых только 2 могут похвастаться стабильностью и сложностью O(n) в лучшем случае. Один из этих двух — это давно и хорошо всем известная «Сортировка с помощью двоичного дерева». А вот второй как-раз таки Timsort.

Алгоритм построен на той идее, что в реальном мире сортируемый массив данных часто содержат в себе упорядоченные (не важно, по возрастанию или по убыванию) подмассивы. Это и вправду часто так. На таких данных Timsort рвёт в клочья все остальные алгоритмы.

Сразу к сути


Не ждите тут каких-то сложных математических открытий. Дело в том, что на самом деле Timsort — это не полностью самостоятельный алгоритм, а гибрид, эффективная комбинация нескольких других алгоритмов, приправленная собственными идеями. Очень коротко суть алгоритма можно объяснить так:
  1. По специальному алгоритму разделяем входной массив на подмассивы.
  2. Сортируем каждый подмассив обычной сортировкой вставками.
  3. Собираем отсортированные подмассивы в единый массив с помощью модифицированной сортировки слиянием.
Дьявол, как всегда, скрывается в деталях, а именно в алгоритме из пункта 1 и модификации сортировки слиянием из пункта 3.

Алгоритм


Используемые понятия
  • N — размер входного массива
  • run — упорядоченный подмассив во входном массиве. Причём упорядоченный либо нестрого по возрастанию, либо строго по убыванию. Т.е или «a0 <= a1 <= a2 <= ...», либо «a0 > a1 > a2 > ...»
  • minrun — как было сказано выше, на первом шаге алгоритма входной массив будет поделен на подмассивы. minrun — это минимальный размер такого подмассива. Это число рассчитывается по определённой логике из числа N.



Шаг 0. Вычисление minrun.

Число minrun определяется на основе N исходя из следующих принципов:
  1. Оно не должно быть слишком большим, поскольку к подмассиву размера minrun будет в дальнейшем применена сортировка вставками, а она эффективна только на небольших массивах
  2. Оно не должно быть слишком маленьким, поскольку чем меньше подмассив — тем больше итераций слияния подмассивов придётся выполнить на последнем шаге алгоритма.
  3. Хорошо бы, чтобы N \ minrun было степенью числа 2 (или близким к нему). Это требование обусловлено тем, что алгоритм слияния подмассивов наиболее эффективно работает на подмассивах примерно равного размера.
В этом месте автор алгоритма ссылается на собственные эксперименты, показавшие, что при minrun> 256 нарушается пункт 1, при minrun < 8 — пункт 2 и наиболее эффективно использовать значения из диапазона (32;65). Исключение — если N < 64, тогда minrun = N и timsort превращается в простую сортировку вставкой. В данный момент алгоритм расчёта minrun просто до безобразия: берём старшие 6 бит из N и добавляем единицу, если в оставшихся младших битах есть хотя бы один ненулевой. Примерный код выглядит так:
	int GetMinrun(int n)
	{
	    int r = 0;           /* станет 1 если среди сдвинутых битов будет хотя бы 1 ненулевой */
	    while (n >= 64) {
	        r |= n & 1;
	        n >>= 1;
	    }
	    return n + r;
	}

Шаг 1. Разбиение на подмассивы и их сортировка.

Итак, на данном этапе у нас есть входной массив, его размер N и вычисленное число minrun. Алгоритм работы этого шага:
  1. Ставим указатель текущего элемента в начало входного массива.
  2. Начиная с текущего элемента, ищем во входном массиве run (упорядоченный подмассив). По определению, в этот run однозначно войдет текущий элемент и следующий за ним, а вот дальше — уже как повезет. Если получившийся подмассив упорядочен по убыванию — переставляем элементы так, чтобы они шли по возрастанию (это простой линейный алгоритм, просто идём с обоих концов к середине, меняя элементы местами).
  3. Если размер текущего run'а меньше чем minrun — берём следующие за найденным run-ом элементы в количестве minrun — size(run). Таким образом, на выходе у нас получается подмассив размером minrun или больше, часть которого (а в идеале — он весь) упорядочена.
  4. Применяем к данному подмассиву сортировку вставками. Так как размер подмассива невелик и часть его уже упорядочена — сортировка работает быстро и эффективно.
  5. Ставим указатель текущего элемента на следующий за подмассивом элемент.
  6. Если конец входного массива не достигнут — переход к пункту 2, иначе — конец данного шага.

Шаг 2. Слияние.

На данном этапе у нас имеется входной массив, разбитый на подмассивы, каждый из которых упорядочен. Если данные входного массива были близки к случайным — размер упорядоченных подмассивов близок к minrun, если в данных были упорядоченные диапазоны (а исходя из рекомендаций по применению алгоритма, у нас есть основания на это надеяться) — упорядоченные подмассивы имеют размер, превышающий minrun.
Теперь нам нужно объединить эти подмассивы для получения результирующего, полностью упорядоченного массива. Причём по ходу этого объединения нужно выполнить 2 требования:
  1. Объединять подмассивы примерно равного размера (так получается эффективнее).
  2. Сохранить стабильность алгоритма — т.е. не делать бессмысленных перестановок (например, не менять два последовательно стоящих одинаковых числа местами).

Достигается это таким образом.
  1. Создаем пустой стек пар <индекс начала подмассива>-<размер подмассива>. Берём первый упорядоченный подмассив.
  2. Добавляем в стек пару данных <индекс начала>-<размер> для текущего подмассива.
  3. Определяем, нужно ли выполнять процедуру слияния текущего подмассива с предыдущими. Для этого проверяется выполнение 2 правил (пусть X, Y и Z — размеры трёх верхних в стеке подмассивов):
    X > Y + Z
    Y > Z
  4. Если одно из правил нарушается — массив Y сливается с меньшим из массивов X и Z. Повторяется до выполнения обоих правил или полного упорядочивания данных.
  5. Если еще остались не рассмотренные подмассивы — берём следующий и переходим к пункту 2. Иначе — конец.

Цель этой хитрой процедуры — сохранение баланса. Т.е. изменения будут выглядеть вот так:

а значит, размеры подмассивов в стеке эффективны для дальнейшей сортировки слиянием. Представьте себе идеальный случай: у нас есть подмассивы размера 128, 64, 32, 16, 8, 4, 2, 2 (забудем на секунду о наличии требования «размер подмассива >= minrun»). В этом случае никаких слияний не будет выполнятся пока не встретятся 2 последних подмассива, а вот после этого будут выполнены 7 идеально сбалансированных слияний.

Процедура слияния подмассивов

Как Вы помните, на втором шаге алгоритма мы занимаемся слиянием двух подмассивов в один упорядоченный. Мы всегда соединяем 2 последовательных подмассива. Для их слияния используется дополнительная память.
  1. Создаём временный массив в размере меньшего из соединяемых подмассивов.
  2. Копируем меньший из подмассивов во временный массив
  3. Ставим указатели текущей позиции на первые элементы большего и временного массива.
  4. На каждом следующем шаге рассматриваем значение текущих элементов в большем и временном массивах, берём меньший из них и копируем его в новый отсортированный массив. Перемещаем указатель текущего элемента в массиве, из которого был взят элемент.
  5. Повторяем 4, пока один из массивов не закончится.
  6. Добавляем все элементы оставшегося массива в конец нового массива.


Модификация процедуры слияния подмассивов

Всё, вроде бы, хорошо в показанном выше алгоритме слияния. Кроме одного. Представьте себе процедуру слияния двух вот таких массивов:
A = {1, 2, 3,..., 9999, 10000}
B = { 20000, 20001, ...., 29999, 30000}
Вышеуказанная процедура для них, конечно, сработает, но каждый раз на её четвёртом пункте нужно будет выполнить одно сравнение и одно копирование. И того 10000 сравнений и 10000 копирований. Алгоритм Timsort предлагает в этом месте модификацию, которую он называет «галоп». Суть в следующем:
  1. Начинаем процедуру слияния, как было показано выше.
  2. На каждой операции копирования элемента из временного или большего подмассива в результирующий запоминаем, из какого именно подмассива был элемент.
  3. Если уже некоторое количество элементов (в данной реализации алгоритма это число жестко равно 7) было взято из одного и того же массива — предполагаем, что и дальше нам придётся брать данные из него. Чтобы подтвердить эту идею, мы переходим в режим «галопа», т.е. бежим по массиву-претенденту на поставку следующей большой порции данных бинарным поиском (мы помним, что массив упорядочен и мы имеем полное право на бинарный поиск) текущего элемента из второго соединяемого массива. Бинарный поиск эффективнее линейного, а потому операций поиска будет намного меньше.
  4. Найдя, наконец, момент, когда данные из текущего массива-поставщика нам больше не подходят (или дойдя до конца массива), мы можем, наконец, скопировать их все разом (что может быть эффективнее копирования одиночных элементов).

Возможно, объяснение слегка туманно, попробуем на примере.
A = {1, 2, 3,..., 9999, 10000}
B = { 20000, 20001, ...., 29999, 30000}
  1. Первые 7 итераций мы сравниваем числа 1, 2, 3, 4, 5, 6 и 7 из массива A с числом 20000 и, убедившись, что 20000 больше — копируем элементы массива A в результирующий.
  2. Начиная со следующей итерации переходим в режим «галопа»: сравниваем с числом 20000 последовательно элементы 8, 10, 14, 22, 38, n+2^i, ..., 10000 массива A. Как видно, таких сравнение будет намного меньше 10000.
  3. Мы дошли до конца массива A и знаем, что он весь меньше B (мы могли также остановиться где-то посередине). Копируем нужные данные из массива A в результирующий, идём дальше.

Вот и весь алгоритм.

Материалы по теме
Автор: @Infopulse_Ukraine

Комментарии (62)

  • +3
    надо будет заимплементить под php
    • +5
      И отхватить много приятных минут на типах, отличных от целого из-за битовых операций.
      • +3
        Можно подробнее, чем помешают битовые операции? Либо я чего-то не понимаю, либо они используются только для вычисления параметра minrun.
    • 0
      Пользовательская реализация все равно будет проигрывать в скорости встроенным алгоритмам. Да и памяти предложенный вариант кушает…
    • +3
      Нужно добавить в sort, ksort krsort и т.п. параметр с дефолтным значением константа SM_QUICKSORT(SM типа Sort Method или чё нить другое) и будет возможность юзать например SM_TIMSORT
  • +59
    Думаю, эта статья могла бы стать русской версией страницы в википедии, если оформить ее по правилам.
    • +36
      Я вот неоднократно сталкивался с тем, что при публикации статьи в Википедию примерно 60% усилий уходит на написание статьи, а еще 40% — на ее оформление по правилам Википедии и доказательство всем окружающим её важности, значимости, достоверности и т.д. После нескольких провалов именно на последнем этапе я навсегда зарёкся писать статьи на Википедию. С Хабром проще — статья по делу будет принята хорошо и без всего этого занудства.
      • –18
        >> После нескольких провалов именно на последнем этапе я навсегда зарёкся писать статьи на Википедию.

        Тяжко вам наверное :)
        • +12
          Да нет, нормально. Я ж не читать, я писать туда перестал.
      • НЛО прилетело и опубликовало эту надпись здесь
        • +6
          Я как бывший «старый пердун-админ» могу сказать, что если вы не про очередного покемона решили писать, то никаких проблем не будет.

          Тут есть один нюанс: писать надо НЕ ИЗ ГОЛОВЫ. А по источникам.
          • +9
            посему сначала надо написать на хабре, а потом на Википедии сослаться на свою же статью как бы со стороны.
            И уже авторитетно...! подкреплено ссылкой...!
            • +2
              Не могу не вспомнить:
              xkcd.com/978/
            • –1
              Именно из-за такой херни у людей возникают проблемы. Хабр — вообще место для блогов. А блог — очевидно не авторитетный источник. Возьмите несколько умных книжек, напишите по ним, в чём проблема-то? Нет, норовят писать из головы, да ещё пытаются подобные нелепые конструкции изобретать.
          • +2
            Тут есть один ньюанс — если я крупный специалист в области, о которой пишу и сам себе источник — то облом.
            А подкрепить любой безумный высер такими же высерамии дурналистов — раз плюнуть.
            Публикация информации и википедическое преломление
            • +1
              Википедия на это отвечает, что мол, «Вики — не место для оригинальных исследований». Т.е. сначала опубликуйтесь где-то, пусть Вас там покритикуют, и, если решат что дело говорите — тогда уж пишите на Вики со ссылкой на публикацию. Они, может быть и правы. Только вот те, кто где-то там опубликуются, тем Вики уже и нафиг не нужна.
              • 0
                Угу. Более того, в силу очевидного конфликта интересов, считается неэтичным ссылаться на свои работы (даже рецензированные) при написании статей. То есть ты тристараз умный, а ссылаться можно только вот на то ничтожество, которое на диссертации подлые вопросы задавало, но никак не на себя умного и объективного.
            • +2
              Да, именно так. Публикация оригинальных исследований запрещена.

              Причина — вы считаете себя крупным специалистом, а окружающие спецы считают вас некрупным прохиндеем, пилящим бюджет на серебрянных фильтрах для воды. Кто прав?

              Википедия не место для публикации _НОВЫХ_ данных, это место для сбора хорошо проверенных и общеизвестных в профессиональных кругах фактов, а так же место для отражения наличия разногласий по вопросу при их наличии.

              Вот именно люди, которые «всё знают и сами себе авторитетный источник» больше всего в википедии страдают, когда их очередную теорию квантово-торсионного излечения ауры (именно в этом вопросе они очень крупные специалисты) сносят за отсутствие источников.

              Если честно, я столько раз это говорил в википедии, что уже повторять лень.

              Нет источников — написано из головы — проверить невозможно — кандидат на удаление. Точка.
    • +19
      Если кому-то хочется — может оформить и выложить. Правила Хабра это позволяют, да и я не против.
  • 0
    Немного не понял почему этот алгоритм лучше чем использование бинарного дерева.
    И здесь, и там O(n) достигается при уже отсортированном массиве.
    • +4
      При уже отсортированном массиве — ничем не лучше. Даже обычной сортировки вставской не лучше. Лучше на массиве, содержащем, скажем, 20 упорядоченных подмассивов, которые, однако, не упорядочены между собой.

      Т.е. проще говоря, идеальные случаи отличаются и, по мнению автора, хорошие для Timsort случаи встречается в реальной жизни чаще хороших случаев других алгоритмов.
      • +2
        А почему не брался в расчет smoothsort? Ведь там память O(1), а все остальные показатели такие же, кроме stable. Stable означает, что рядом стоящие элементы в правильном порядке не будут переставляться?
        На больших массивах выделение памяти имеет значение и на очень маленьких тоже.
        • +2
          Никто и не спорит, что другие алгоритмы имеют право на жизнь, статья описывает только достоинства и недостатки данного алгоритма. А что и когда использовать — решать нужно в каждом конкретном случае. «Стабильность», к стати, означает еще и то, что если в сортируемом массиве встретятся подряд идущие одинаковые элементы — стабильный метод их переставлять не будет, а нестабильный волен хоть 100 раз их перетасовать.

          Я так думаю, что лучшее применение этой штуки — например, слить в одну пару таблиц из базы или листов из экселевской книги. Частично отсортированные данные, величины порядка тысяч\миллионов записей — самое то.
          • 0
            Если уже некоторое количество элементов (в данной реализации алгоритма это число жестко равно 7) было взято из одного и того же массива — предполагаем, что и дальше нам придётся брать данные из него.

            А нельзя, дополнительно перед слиянием, сравнить границы сливаемых массивов, чтобы в случае вашего примера сразу последовательно переписать массивы в результирующий?
          • НЛО прилетело и опубликовало эту надпись здесь
  • +8
    Замечательная статья! Не хватает только одного: сравнения Timsort и Binary tree sort, ведь у них равные параметры.
    • +3
      Почитайте статьи по ссылкам в конце статьи. Там есть результаты сравнения с некоторыми другими алгоритмами.
  • +5
    Небольшое замечание по поводу сравнения с другими алгоритмами — оно не совсем корректное: TimSort следует сравнивать по трудоемкости со стабильными алгоритмами сортировки сравнениями.

    А в таблице каша получается: намешаны алгоритмы разного типа. Если уж перечислять, то добавьте и Bucket Sort, которая всегда O(n) по трудоемкости.

    А вообще разных более или менее хороших алгоритмов гораздо больше, чем приведено здесь. И вообще не понятно, зачем сравнивать с заведомо проигрышным Bogosort, который нигде и не используется наверно )
    • +3
      Табличка просто взята с Википедии ввиду того, что таблички размером побольше нигде найдено не было. Ясное дело, что алгоритмов намного больше, и понятно, что Timsort не «предел мечтаний». Просто у него тоже есть своя ниша, а статья — всего лишь его описание.
      • 0
        ну я же вас не обвиняю ) просто сделал «небольшое замечание» по содержанию статьи. мб стоит тогда ее перенести в раздел Перевод, если непосредственно вашего текста там нет?
        • +4
          Это не перевод. Это компиляция примерно десятка статей, с собственными примерами и пояснениями. Собственно говоря, ни одного предложения просто «в лоб» переведённого в статье нет.
    • 0
      к слову о таблице «из википедии». как среднее может быть равно худшему, когда лучшее не равно ни тому ни другому?
      • 0
        А где противоречие?
        • 0
          пример в действительных числах осилите? хотя бы одну подборочку.
      • +3
        вы, видимо, не совсем правильно понимаете сложность алгоритма, здесь не говорится, что время работы алгоритма в среднем и в худшем случае равны, равна только их сложность, т.е. зависимость от размера входных данных
  • +1
    Отдалённо этот алгоритм похож на сортировку Шелла, которой тоже сливаются частично упорядоченные массивы.
  • 0
    А какой у них коэфициент? Дерево вроде тоже в апроксимации хорошо, но… затратно
    • +1
      Если Вы об использовании памяти, то Timsort в самом худшем случае требует 0.5*N памяти. Если о лучшем случае — то коэфициент чётко 1 (т.е. нужно будет ровно N операций сравнения).
      • 0
        нет. g(x) = O(f(x)) это «упрощенно» g(x) < C * f(x) на ассимптотике.

        Так вот, не смотря на то, что quick имеет в худшем случае O(n^2), он при этом имеет C значительно меньше, чем сортировка деревом и работает обычно быстрее.
        • 0
          Вы знаете, серьёзных фундаментальных исследований на эту тему по Timsort я нигде не встречал. В оригинальной статье (ссылка в конце статьи) автор алгоритма сравнивает Timsort с samplesort, quicksort и mergesort и показывает (в основном, по факту тестов, а не теоретически) преимущество Timsort над ними в пределах от 1.5% скорости до вообще нереальных чисел.
  • 0
    чем этот хитрый алгоритм лучше бинарного дерева?
    • 0
      Если бы он был однозначно «лучше» — то дерева бинарного уже давно не существовало бы. Меньше памяти кушает, на определённых данных быстрее работает (а на других данных — лучше дерево).
  • +1
    Интересно было бы иметь какой-то (статистический?) метод, позволяющий в зависимости от контента переключаться между бинарным деревом и тимсортом
  • 0
    Что-то я не понял, это в асимптотике тимсорт в лучшем случае работает за O(n)?
    Странно, лично мне показалось, что на лучшем наборе он работает за такое время только, когда используется сортировка вставками (ибо последовательность может быть уже отсортирована, тогда вставки работают за O(n)) значит она может работать с O(n) только до minrun, до дальше работает слияние, но слияния, в свою очередь, будут работать в лучшем случае O(nlogn) значит и весь алгоритм в асимптотике будет работать за O(nlogn). Так что я ставлю под сомнение вообще достоверность всей таблички в статье, и не правомерно сравнивать алгоритмы для которых асимптотики написаны не верно — «левые»…
    К примеру, мне интересно, а зачем нужна память в быстрой сортировке? Я раньше думал, что не нужна, ибо сортировка идёт «на месте».
    Затем, я думал, что в лучшем случае, для сортировки слиянием потребуется память O(n), конечно если не использовать Алгоритм Пратта (точно не помню как его зовут, может и не Пратт) или другие методы связанные с медианами (асимптотика которых написана на третьей строке таблицы), значит уже 3 ошибки в таблице. Причём одна из них связанна с повествуемым материалом, который сравнивается с методом сортировки бинарным деревом, у которого коэффициенты у сложности намного больше даже чем у сортировки слиянием (ибо приходится уравновешивать дерево, а иначе он будет работать не быстрее быстрой сортировки на плохом случае, т.е. за O(n^2))

    «На таких данных Timsort рвёт в клочья все остальные алгоритмы. » — конечно конечно, если считать что он асимптотически на лучшем наборе работает за O(nlogn), коих результатов не может добиться ни один алгоритм (сарказм).
    • +1
      > К примеру, мне интересно, а зачем нужна память в быстрой сортировке?

      Для хранения стека…
      • 0
        В статье говорят об алгоритмах, а не о реализации алгоритма на каком либо языке. К примеру, есть такая вещь как хвостовая рекурсия. Она реализована не во всех языках, но она существует и она не требует памяти для хранения точки возврата из функции в стеке, возврата не происходит.
        Если какой-то язык не реализует что-то необходимое для реализации алгоритма, это ещё не значит что алгоритм работает медленно или использует больше места.
        • +1
          Извините, но быстрой сортировке в любой реализации нужен стек, то ли вы его сами делаете (итеративный вариант), то ли система его делает за вас (рекурсивный вариант). Можете почитать любую книгу по анализу алгоритмов (передо мной сейчас лежит Седжвик). Хвостовая рекурсия здесь вообще не причем, т. к. в быстрой сортировке два рекурсивных вызова…
          • –1
            Седжвик пишет про реализации алгоритмов на C/C++… Реализацию алгоритма на некотором языке.
            Его анализ идёт в рамках данного языка, да, в C/C++ нет средств (хотя я не знаю) оптимизации к хвостовой рекурсии на уровне компилятора, поэтому для данных языков это верно.
            ru.wikipedia.org/wiki/%D0%A5%D0%B2%D0%BE%D1%81%D1%82%D0%BE%D0%B2%D0%B0%D1%8F_%D1%80%D0%B5%D0%BA%D1%83%D1%80%D1%81%D0%B8%D1%8F
            См. раздел «описание». Примечание: причём возрат в функции это void.
            • +3
              Последний раз повторяю, для тех, кто в танке (:
              1) Стек нужен в любой реализации быстрой сортировки — если вам не нравится Седжвик, то загляните в Кормена (там C/С++ нет).
              2) Хвостовой рекурсии в быстрой сортировке нет, т. к. в ней имеется два рекурсивных вызова. В том же Кормене есть упражнение, в котором описывается как избавиться только от одного рекурсивного вызова (при этом размер стека все равно в лучшем случае будет равен log(n)…
              • 0
                Для тех кто не в танке :)) выложу скрины со страниц Кормена, вынудили, обращаю внимание на второй скрин в нём говорится о реализации Седжвика…
                dl.dropbox.com/u/5753856/%D1%81%D0%BA%D1%80%D0%B8%D0%BD1.png

                dl.dropbox.com/u/5753856/%D1%81%D0%BA%D1%80%D0%B8%D0%BD1.png

                Первый скрин страница 198, второй скрин страница 219
                • 0
                • +1
                  Дополнительная память не нужна для хранения элементов массива, но она используется для организации вычислений… А насчет стека загляните на страницу 217, упражнение 7.4
        • 0
          Вообщем мелкие массивы он сортирует со скоростью вставками, т.е. за n операций, для больших массивов (больше 64), его асимптотика равна асимптотике сортировки слияние, т.е. за nlogn. А значит тут вообще говорить о том, что алгоритм работает с такой же скоростью в асимптотике, что и сортировка бинарного дерева, не корректно.
          • +2
            Ошибка в Ваших размышлениях вот тут:
            >«значит она может работать с O(n) только до minrun»

            minrun — это не константный и не максимальный, а минимальный размер отсортированного подмассива. В алгоритме шага №1 (пункты 2 и 3) написано, что ищется максимальный размер run, который в идеале будет равен N, а значит никаких сортировок вообще применено не будет.
            • +1
              Мой феил, согласен с этим. Действительно асимптотика сложности снизу равна P(n) для всех n.
  • 0
    исходник на Java
  • 0
    Причём упорядоченный либо нестрого по возрастанию, либо строго по убыванию. Т.е или «a0 <= a1 <= a2 <= ...», либо «a0 > a1 > a2 > ...»


    Почему либо строго по убыванию? Это ведь нужно для разделения на подмассивы?
    • 0
      блин, туплю. для сохранения стабильности при развороте массива=)
  • +1
    Вкусненько, спасибо за статью.

  • 0
    Выяснилось, что это чудо всё это время содержало в себе ошибку:
    xakep.ru/2015/02/25/timsort-bug/

Только зарегистрированные пользователи могут оставлять комментарии. Войдите, пожалуйста.

Самое читаемое Разработка