Изменения

Алгоритм построен на основе экспоненциального поискового дерева (далее {{---}} Э.П.ЭП-дерево) Андерсона (Andersson's exponential search tree). Сортировка происходит за счет вставки целых чисел в Э.П.ЭП-дерево.

Э.П.ЭП-дерево с <tex>n</tex> листьями состоит из корня <tex>r</tex> и <tex>n^e</tex> (0<<tex>e</tex><1) Э.П.ЭП-поддеревьев, в каждом из которых <tex>n^{1 - e}</tex> листьев; каждое Э.П.ЭП-поддерево является сыном корня <tex>r</tex>. В этом дереве <tex>O(n \log\log n)</tex> уровней. При нарушении баланса дерева, необходимо балансирование, которое требует <tex>O(n \log\log n)</tex> времени при <tex>n</tex> вставленных целых числах. Такое время достигается за счет вставки чисел группами, а не по одиночке, как изначально предлагает Андерссон.

Берем <tex>1/e = 5</tex> для экспоненциального поискового дереве Андерссона. Поэтому у корня будет <tex>n^{1/5}</tex> детей и каждое Э.П.ЭП-дерево в каждом ребенке будет иметь <tex>n^{4/5}</tex> листьев. В отличии от оригинального дерева, мы будем вставлять не один элемент за раз а <tex>d^2</tex>, где <tex>d</tex> {{---}} количество детей узла дерева, где числа должны спуститься вниз.Но мы не будем сразу опускать донизу все <tex>d^2</tex> чисел. Мы будем полностью опускать все <tex>d^2</tex> чисел на один уровень. В корне мы опустим <tex>n^{2/5}</tex> чисел на следующий уровень. После того, как мы опустили все числа на следующий уровень мы успешно разделили числа на <tex>t_{1} = n^{1/5}</tex> наборов <tex>S_{1}, S_{2}, ..., S_{t_{1}}</tex>, в каждом из которых <tex>n^{4/5}</tex> чисел и <tex>S_{i} < S_{j}, i < j</tex>. Затем мы берем <tex>n^{(4/5)(2/5)}</tex> чисел из <tex>S_{i}</tex> за раз и опускаем их на следующий уровень Э.П.ЭП-дерева. Повторяем это, пока все числа не опустятся на следующий уровень. На этом шаге мы разделили числа на <tex>t_{2} = n^{1/5}n^{4/25} = n^{9/25}</tex> наборов <tex>T_{1}, T_{2}, ..., T_{t_{2}}</tex> в каждом из которых <tex>n^{16/25}</tex> чисел, аналогичным наборам <tex>S_{i}</tex>. Теперь мы можем дальше опустить числа в нашем Э.П.ЭП-дереве.

Нетрудно заметить, что ребалансирока занимает <tex>O(n \log\log n)</tex> времени с <tex>O(n)</tex> временем на уровень. Аналогично стандартному Э.П.ЭП-дереву Андерссона.

Нам следует нумеровать уровни Э.П.ЭП-дерева с корня, начиная с нуля. Рассмотрим спуск вниз на уровне <tex>s</tex>. Мы имеем <tex>t = n^{1 - (4/5)^s}</tex> наборов по <tex>n^{(4/5)^s}</tex> чисел в каждом. Так как каждый узел на данном уровне имеет <tex>p = n^{(1/5)(4/5)^s}</tex> детей, то на <tex>s + 1</tex> уровень мы опустим <tex>q = n^{(2/5)(4/5)^s}</tex> чисел для каждого набора или всего <tex>qt \ge n^{2/5}</tex> чисел для всех наборов за один раз.

Спуск вниз можно рассматривать как сортировку <tex>q</tex> чисел в каждом наборе вместе с <tex>p</tex> числами <tex>a_{1}, a_{2}, ..., a_{p}</tex> из Э.П.ЭП-дерева, так, что эти <tex>q</tex> чисел разделены в <tex>p + 1</tex> наборов <tex>S_{0}, S_{1}, ..., S_{p}</tex> таких, что <tex>S_{0} < </tex>{<tex>a_{1}</tex>} < ... < {<tex>a_{p}</tex>}<tex> < S_{p}</tex>.

Теперь рассмотрим проблему упаковки, которую решим следующим образом. Будем считать что число бит в контейнере <tex>\log m \ge \log\log\log n</tex>, потому, что в противном случае можно использовать radix sort для сортировки чисел. У контейнера есть <tex>h/ \log\log n</tex> хэшированных значений (сегментов) в себе на уровне <tex>\log h</tex> в Э.П.ЭП-дереве. Полное число хэшированных бит в контейнере <tex>(2 \log n)(c \log\log n)</tex> бит. Хотя хэшированны биты в контейнере выглядят как <tex>0^{i}t_{1}0^{i}t_{2}...t_{h/ \log\log n}</tex>, где <tex>t_{k}</tex>-ые это хэшированные биты, а нули это просто нули. Сначала упаковываем <tex>\log\log n</tex> контейнеров в один и получаем <tex>w_{1} = 0^{j}t_{1, 1}t_{2, 1}...t_{\log\log n, 1}0^{j}t_{1, 2}...t_{\log\log n, h/ \log\log n}</tex> где <tex>t_{i, k}</tex>: <tex>k = 1, 2, ..., h/ \log\log n</tex> из <tex>i</tex>-ого контейнера. мы ипользуем <tex>O(\log\log n)</tex> шагов, чтобы упаковать <tex>w_{1}</tex> в <tex>w_{2} = 0^{jh/ \log\log n}t_{1, 1}t_{2, 1} ... t_{\log\log n, 1}t_{1, 2}t_{2, 2} ... t_{1, h/ \log\log n}t_{2, h/ \log\log n} ... t_{\log\log n, h/ \log\log n}</tex>. Теперь упакованные хэш биты занимают <tex>2 \log n/c</tex> бит. Мы используем <tex>O(\log\log n)</tex> времени чтобы распаковать <tex>w_{2}</tex> в <tex>\log\log n</tex> контейнеров <tex>w_{3, k} = 0^{jh/ \log\log n}0^{r}t_{k, 1}O^{r}t_{k, 2} ... t_{k, h/ \log\log n} k = 1, 2, ..., \log\log n</tex>. Затем используя <tex>O(\log\log n)</tex> времени упаковываем эти <tex>\log\log n</tex> контейнеров в один <tex>w_{4} = 0^{r}t_{1, 1}0^{r}t_{1, 2} ... t_{1, h/ \log\log n}0^{r}t_{2, 1} ... t_{\log\log n, h/ \log\log n}</tex>. Затем используя <tex>O(\log\log n)</tex> шагов упаковать <tex>w_{4}</tex> в <tex>w_{5} = 0^{s}t_{1, 1}t_{1, 2} ... t_{1, h/ \log\log n}t_{2, 1}t_{2, 2} ... t_{\log\log n, h/ \log\log n}</tex>. В итоге мы используем <tex>O(\log\log n)</tex> времени для упаковки <tex>\log\log n</tex> контейнеров. Считаем что время потраченное на одно слово {{---}} константа.