Sieci sortujące artykuł 1

Abstrakcja

Celem tego artykułu jest opisanie sieci sortujących o wielkości 0 (nlogn) i głębokości 0 (nlogn).

Naturalnym sposobem sortowania jest ustalenie kolejnych podziałów: ustalenie górnej i dolnej połówki ciągu, postępowanie podobne z każdą następną połówką i tak dalej. Niestety, kiedy jedno przepołowienie ciągu używa tylko 0 (n) porównań, czas (równoległy) jego wykonania nie może być mniejszy niż logn. Wiadomo, że sieć przepoławiająca używa 0,5logn porównań.

Jest jednak możliwe stworzenie sieci 0 (n) porównań, która przeprowadza dzielenie w stałym czasie z wysoką dokładnością. Procedura (ε-przepoławianie) i wykorzystująca ją procedura (ε-sortowanie) są opisane poniżej. Nasza sieć sortująca koncentruje się na tych podstawowych krokach.

Wprowadzenie

Sieć opisana abstrakcyjnie jest siecią porównującą, zdeterminowaną sekwencją 0 (nlogn) zamian, gdzie zamiana następuje na parze (i,j), gdzie
i operacja ta jest następująca: porównuje się aktualną wartość elementu i-tego i j-tego oraz (jeśli to konieczne, zamienia się ich kolejność) umieszcza się większy element w miejsce j, a mniejszy w miejsce i. Na końcu algorytmu najmniejszy element i znajduje się w rejestrze elementu i-tego dla i=1,2,…,n. Z zasady, elementy są posortowane.

Algorytm działa przy 0 (logn) opóźnieniu czasu (czas równoległy). Powinniśmy wspomnieć, że stała biorąca udział w 0 (.) jest bardzo duża i zdeterminowana przez rozmiar grafów o ścieżkach rozrastających się. Czyni to algorytm nie pasującym do aktualnej implementacji i znacznie wolniejszym niż np.: algorytm Batchera dla „małych” wartości n. (Stałe mogą być drastycznie zredukowane przez wygenerowanie losowych grafów, w przeciwieństwie do użycia znanych konstrukcji). Jest to próba osiągnięcia najlepszych możliwych do osiągnięcia stałych.

Wcześniejsza wersja tego algorytmu jest zakorzeniona w kombinatoryce. Mimo, że główne idee są w całości zawarte w artykule, dwa formalne zapisy są tak od siebie różne, że warto zaprezentować tę drugą wersję.

Zaczniemy od krótkiego, nieformalnego opisu naszego algorytmu. Został dostarczony przez Joela Spencera, za co jesteśmy mu bardzo wdzięczni. To skłoniło nas do napisania tego artykułu niezwłocznie.

Zarys Spencera zostanie poprzedzony krótkim wstępem o grafach ze ścieżkami rozrastającymi się. Pozostała część artykułu została zapełniona detalami nieformalnego opisu.

Opis Spencera

Są trzy kroki: ε-przepoławianie, ε-sortowanie i algorytm. Na szczęście do każdej z tych części potrzebujemy jedynie wyjaśnienia części poprzedniej.

ε-przepoławianie. ε jest ustalone, powiedzmy ε =
. W ustalonym, skończonym czasie (czas jest równy n/2 porównań), ε-połówkowanie m rejestrów umieści połowę liczb o mniejszej wartości w dolnej połowie rejestrów, z popełnieniem co najwyżej εm błędów. I każdego k,
, pierwsze liczby k znajdują się w dolnej połowie rejestrów z popełnieniem co najwyżej εk błędów (i podobnie z kolejnymi numerami k). Te ε-przepoławiania są ściśle związane z grafami o ścieżkach rozszerzających się. Myślę, że w każdej jednostce czasu wymagane jest losowe l-dzieleń, żeby utworzyć podział liczb na dolną połówkę, i górną połówką rejestrów, co tworzy obliczenia probabilistyczne.

ε-sortowanie. ε jest ustalone. Powiedzmy ε =
. W ustalonym, skończonym czasie ε-sortowanie umieszcza zawartości 1,…,m w rejestry 1,…,m, tak, że dla wszystkich odstępów czasu I, dla każdego z rejestrów, odpowiedni numer znajdzie się w I (nie koniecznie w kolejności) z popełnieniem co najwyżej εm błędów i dla każdego k,
, pierwsze k znajdą się w dolnych rejestrach εm przy popełnieniu co najwyżej εk błędów. By stworzyć sortowanie trzeba zastosować ε-przepoławianie (ε =
) do całego ciągu rejestrów. Wówczas je zastosować dla góry i środka połowy rejestrów, potem dla ćwiartki, ósmej części, szesnastej części, itd., dopóki kawałki nie będą miały rozmiaru m=
. Można szybko pokazać, że każdy kawałek o wielkości w=m*
zawiera co najwyżej εw błędów. Kawałki są małe, od kiedy
i ta część twierdzenia nie jest zbyt trudna.

Algorytm. W pewym sensie algorytm jest prosty do opisania. N rejestrów zostaje ponumerowanych od 1 do n. Dla każdego i,
dany jest podział rejestrów. Te podziały są wyraźnie dane i całkowicie niezależne od zawartości rejestrów. Dla danego i przygotowujemy oddzielne sortowanie (mające miejsce w tym samym czasie) dla każdego ciągu i-tego przedziału.

Opis przedziału w formie drzewa binarnego jest użyteczny. Rozważmy binarne, planarne drzewo. W czasie t prowadzimy rejestry do węzłów, jak pokazano. Nie ma rejestrów na wyższym poziomie niż t. Dla każdego węzła istnieje naturalny przedział w rejestrach - dla źródła wszystkich i dla oznaczonego węzła (n/4+1;2n/4). (Ten przedział jest interpretowany jako estymator dla zawartości rejestrów przypisanych do węzła.)

Węzeł na poziomie t po raz pierwszy występuje w czasie t i wówczas posiada kompletny, naturalny przedział, poza tym, co zostało wykorzystane nad nim. (W pewnym sensie wyższy węzeł ma wyższy priorytet.) Węzeł na poziomie t w czasie t+1 ma dwie szczeliny rejestrowe - na każdej krawędzi jego naturalnej szczeliny. (Będzie tak blisko krawędzi jak to tylko możliwe, ale wyższy węzeł ma pierwszeństwo. A=100, co jest absolutną stałą. A<<1/ ε) Oto trójkąt węzłów i rejestrów, które reprezentują. Każdy przedział Y i Z jest A=100 razy taki jak przedział X.

W czasie t umiejscawiamy (mentalnie) rejestry w tym drzewie binarnym. Podział drzewa na trójkąty z wierzchołkiem w węźle o nieparzystym poziomie. Ten podział rejestrów zastosuje się do ε-sortowania na każdy trójkąt rejestrów. To jest krok ZIG. Teraz podzielmy drzewo na trójkąty z wierzchołkami w parzystym poziomie węzłów. Zastosować ε-sortowanie do każdego trójkąta. To jest krok ZAG. Wykonać ZIG ZAG ZIG (Nazywamy krok ZIG ZAG ZIG jedną jednostką czasu.)

Teraz czas zamienia się na t+1. Mentalnie przenosimy rejestry do drzewa binarnego (myślę o tym jako o kroku Bookkeeper, ale należy zauważyć, że nie zawiera żadnego czasu i nie wymaga żadnych porównań).Wtedy należy przygotować następny krok ZIG ZAG ZIG. Robimy to logn razy. (Możemy myśleć, że wszystkie rejestry leżą na tym samym korzeniu o czasie 0. Gdy biegnie czas, filtrują się do środka drzewa, ale jeśli pozycja rejestru jest bliska an
, zaczyna się unosić do poziomu s jako rejestr ekstremalny). Twierdzenie mówi, że po takiej procedurze, liczby są posortowane.

Żeby udowodnić prawdziwość tego algorytmu, potrzeba odpowiedniej indukcji tej hipotezy. Przy danym czasie rejestr R z zawartością x leży na węźle n. Oznaczamy błąd jako w(R). Dla jakiegokolwiek węzła n pokrywa się naturalny przedział rejestrów i stąd wynika I(n). Jeśli
wtedy w(R)=0 , rejestr R me odpowiadający numer. W przeciwnym wypadku należy spojrzeć na węzeł
znajdujący się nad N z przedziałem I(
), dublującym I(N). Jeśli
wtedy w(R)=1. Inaczej w(R) jest najmniejszym w, tak, że
, gdzie
jest węzłem oddalonym o dokładnie w poziomów w dół nad N. Dobrze zdefiniowane jest, kiedy źródłowy węzeł N ma przedział I(N) dokładnie takich samych liczb. Na przykład, niech R będzie rejestrem w węźle oznaczonym na diagramie na poprzedniej stronie. Niech x będzie zawartością. (Możemy zauważyć, że zawartości również należą do 1,…,n.) Jeśli 0<x<n/4 i jeśli n/2<x<n, wtedy w(R)=2. Skoro jeden musi iść do źródła, przed poprawnym umiejscowieniem x.

Teraz dla indukcji hipotetycznej. Spoglądając na jakikolwiek węzeł, w jakimkolwiek czasie i niech r będzie dowolną dodatnią liczbą całkowitą. Ułamek rejestrów na tym węźle z błędem
r wynosi co najwyżej
.

Na końcu jedyny węzeł znajduje się w środku i zawiera tylko jeden rejestr i w ten sposób, żaden z rejestrów nie zawiera błędów.

Indukcja występuje w czasie t. Jednostka czasu składa się z dwóch części. W kroku bookkeeping mylność rośnie. Kluczowy krok w czasie występuje, kiedy na poziomie t, węzły łączą się i przechodzą swoimi lewymi i prawymi rozgałęzieniami do poziomu t+1, zachowując swoje ekstrema. Do węzła zastosowano ε-sortowanie, ale ułamek rejestrów ε, które są prawidłowe (błąd=0) posiada stopień błędu =1. Także, wszystkie rejestry, które mają błąd
teraz mają błąd r+1. To naturalne, dlatego podczas procedury bookkeeping stwierdzamy doskonalenie liczb i tak zmniejszamy błąd. W kroku ZIG ZAG ZIG mylność się zmniejsza. (Dokładnie - wykonajmy ZIG ZAG ZIG ZAG ZIG ZAG, dlatego nie martwimy się o stałą.) Spójrzmy na trójkąt XYZ i rozważmy błąd rejestrów Y. Kiedy błąd=1 , powinny znajdować się w Z i te numery powinny przenieść się do rejestrów w X lub Z i zmniejszyć stopień błędu. Jeśli mylność >1, powinny być mniejsze od I(X), pierwsze elementy z pierwszego segmentu zostaną przez ε-sortowanie prawie wszystkie umieszczone w X (będąc w krańcu lewym obrazka X-Y-Z), zmniejszając błąd do 1. Jeśli, powiedzmy, że błąd jest duży, ekspander podniesie liczby przez drugi krok ZIG ZAG ZIG - X będzie częścią większego trójkąta A-X-V i pójdzie do wierzchołka A. Zauważmy, że na obrazku X-Y-Z lewy X wynosi tylko .01 obrazka, ale to wystarczająco, kiedy liczba błędów wynosi około jednego na milion.

Ekspandery

Notacja. Mamy graf G=(V,E) i zestaw
wierzchołków, piszemy
dla zestawu sąsiadów

dla niektórych a
A

Dane są dwa zestawy
, rozdwojony graf G z zestawem wierzchołków
jest nazywany ekspanderem z parametrami
, jeśli dla jakiegokolwiek zestawu

mamy

I tą samą właściwość posiada podzestaw
i nadal maksymalna walencyjność nie przekracza c (i dlatego G ma tylko linową liczbę krawędzi).

Definicja przedstawiona wyżej diametralnie różni się od zwyczajowo przyjętej.

Następująca teoria jest wynikiem pracy kilku uczonych.

Teoria. Dla dowolnego
i
,
>1 oraz
>0, przy czym
istnieje takie c, że c=c(
, tak, że istnieje ekspander z parametrami
dla wszystkich n.

Uwaga. Warunek |A|=|B| w definicji nie jest kompletny. Będziemy także używać ekspanderów dla |A|=|B|+1.

Komentarz. Pierwsze odkrycia na temat istnienia ekspanderów zawdzięczamy Pinskerowi (1973).

Pierwsza wyraźna konstrukcja została stworzona przez Margoulusa (1973) i chociaż grafy same w sobie mają bardzo prostą strukturę, dowód na ich ekspanderskie właściwości opiera się na teorii reprezentacji grup.

Po tych bojach, Gabber i Galil (1979) przyczynili się do powstania bardziej dokładnego dowodu (używając analizy Fouriera), co prowadzi do efektywniejszego szacowania (
) rozrostu.

(Graf biorący udział w wynikach Gaber-Galil -modyfikacja grafu Margoulusa - jest warta wspomnienia, z powodu jego prostoty.

Z (co najwyżej) pięcioma krawędziami wychodzącymi z każdego wierzchołka (i,j) (powiedzmy w
), które nazywają się (i,j), (i, i+j), (i+j, j), (i, i+j+1), (i+j+1, j) (w
), gdzie obliczenia są mod m.

Żeby zrozumieć, dlaczego Margoulus użył transformacji liniowej, a nie rzeczywistej, przeczytaj Klawe (1981). Udowodniła, że jednowymiarowa liniowa transformata (używana do generowania pseudo-losowych liczb) nie zadziała.

By wiedzieć więcej o ekspanderach i superkoncentratorach przeczytaj Valianta (1975), Paula-Tarjana-Celeni (1976), Pipingera (1979), Angluina (1979).

Znana konstrukcja prowadzi do ekspandera arbitralnie wielkiego
przez formowanie wysokiej mocy grafu. Cena jednakże też jest wysoka. Wyżej wspomniana konstrukcja prowadzi do ekspandera z
=2 i (
) tylko dla c rzędu
. Sprawdzamy argumenty, czy istnieje ekspander z parametrami (2,1/3,8). Astronomiczna szczelina 8-
poddaje pod wątpliwość, że warto pracować na dokładnej konstrukcji. (Proste obliczenia pokazują, że graf składający się z c wybranego losowo przez jedno dzielenie, z wysokim prawdopodobieństwem, będzie ekspanderem z parametrami
, jeśli tylko

Kiedy równanie na górze da coś podobnego do

Warto zapamiętać, że generowanie losowego dzielnika wymaga wygenerowania losowej permutacji.)

ε-połówkowanie

Permutacja
ze zbioru (1,2,…,m) została ε-społówkowana, jeśli dla każdego początkowego segmentu S=(1,…,k), gdzie
,
występuje dla co najwyżej ε|S| liczb
i dla każdego końcowego segmentu S=(k,…,m),
,
występuje dla co najwyżej ε|S| liczb
. (Innymi słowy, dwie połowy mają bardzo mało błędów i w większości koncentrują się „po środku”.)

Procedura nazwana jest ε-połówkowaniem (m elementów) jeśli akceptuje permutację 1,…,m jako parametr wejściowy, a jako argument wyjściowy pojawi się ε-społówkowana permutacja 1,…,m.

Skonstruujemy teraz ograniczonej głębokości ε-połówkującą sieć. Wypełniono parzysty ekspander parametrami ((1- ε)/ ε; ε;c), do rejestrów zamieszczono

Połączyć graf w c jednym czynnikiem F1,…,Fc. Interpretując krawędzie jednego czynnika jako zamianę (wykonać porównania samych krawędzi i zawsze umieścić mniejszy element w A), uzyskujemy sieć o głębokości c. Twierdzimy, że to ε-połówka.

Komparator sieci jest zdefiniowany przez jakikolwiek graf rozdzielny na dwa podgrafy, który ma właściwość, że jeśli
i
są połączone przez krawędź, wtedy zawartość
jest mniejsza niż zawartość
. Faktycznie, był etap (kiedy po prostu porównywaliśmy
i
), kiedy było to prawdą, i zawartość
malała, gdy
rosła w tym samym czasie.

Zakładając teraz, że dla niektórych
, więcej niż εk elementów z S=(1,…,k) wyląduje w rejestrze B. Dlatego więcej niż εk wierzchołków w B jest połączonych z co najmniej (1- ε)k wierzchołkami w A, bo musimy mieć parę rejestrów
i
, takich, że
przechowuje element ze zbioru S,
przechowuje element spoza zbioru S, oraz
i
są połączone krawędzią. To, jednakże, zaprzecza wyżej wspomnianej właściwości, gdzie jakikolwiek element S jest mniejszy niż jakikolwiek element spoza S (pierwszy segment)

ε-sortowanie

Notacja. Dana jest permutacja
ze zbioru (1,2,…,m) i podzbiór S z elementów [m]=(1,2,…,m), piszemy, że:

Dane
oznacza zestaw:

dla pewnych i
S

Dokładniej, jeśli
jest segmentem (a,a+1,…,b) to wtedy
jest segmentem (a',a'+1,…,b'), gdzie

Mówimy, że permutacja
ze zbioru (1,2,…,m) jest ε-posortowana, jeśli:

Jest prawdziwe dla każdego początkowego segmentu S=(l,…,k) i końcowego segmentu S=(k,…,m),
.

Procedura nazywana jest ε-sortowaniem (m elementów), jeśli akceptowana jest permutacja l,…,m na wejściu, a na wyjściu pojawia się produkt ε-sortowania - permutacja l,…,m.

Uwaga. Równanie wyżej jasno pokazuje, że

I stosuje się do wszystkich segmentów S=(a,…,b).

Zauważ, że „środkowe” segmenty mają absolutne ograniczenie 3εm, dopóki dla początkowego (i końcowego) segmentu nie zostaną wprowadzone zależne ograniczenia, ważne nawet dla bardzo krótkich segmentów. To spowoduje, że będziemy w stanie uzyskać , przez powtarzanie formuły ε-sortowania, wykładniczego rozkładu błędów.

ε-sortowanie i ε-połówkowanie zwykle są stosowane do sekwencji
, gdzie
jest permutacją uporządkowanego ciągu
. W tym wypadku uważamy elementy
jako zastępcze za 1,…,m.

Do skonstruowania sieci sortującej, zastosuj
-połówkę (sieć), z
<
, dla całego zestawu rejestrów, wtedy zastosuj
-połówkę w stosunku do góry i środka połowy rejestrów, potem do ćwiartki, jednej ósmej, szesnastej, itd, dopóki kawałek nie będzie miał wielkości w< εm. Łatwo zauważyć, że uzyskana sieć o ograniczonej głębokości jest ε-sortowaniem.

Wyznaczona strategia rejestrów

Zamierzamy użyć parametru A>10, której wartość będzie omówiona w sekcji dowodu. Wszystkie logarytmy mają podstawę 2, i przyjmujemy, że n i A są potęgami liczby 2.

Zdefiniujmy następujące liczby:

t=1,2,…,logn i=1,2,…,t

gdzie c=1/(2A), i interpretujemy
jako zero dla i
0.

W czasie t, rejestry przypisują się do j-tego węzła na i-tym poziomie,

formują dwa przedziały
.

jeśli j jest nieparzyste.

jeśli j jest parzyste.

Rejestry przypisane w j-tym węźle na i-tym poziomie,
formują jeden przedział J.

jeśli j jest nieparzyste

jeśli j jest parzyste

Dynamika. Czas rośnie z t do t+1, ponownie umieszczamy rejestry w węzłach. Analizując formuły na górze, można zobaczyć, że proporcjonalnie jakieś 1/A przedziałów pozostaje niezmienione, jednak większość rejestrów z przedziałów przesuwają się o jeden, lub poziomy w dół (pół na pół). Żaden rejestr nie przesuwa się w górę, i A>2 zapewnia, że żaden rejestr nie przesuwa się w dół więcej niż dwa poziomy (
). Te fakty zostaną użyte przy dowodzie.

Po wykonaniu logn/log(2A) kroków, drzewo rozdziela się na dwa drzewa, i potem bardzo szybko rozpada się na małe drzewa. Dlatego nie ma żadnych przemieszczeń elementów między rozłączonymi drzewami, do czasu aż analogiczne przedziały elementów powinny być (i będą) całkowicie uporządkowane między sobą.

Podziały

Chociaż podziały 3t+1 będą wystarczające (trzy w każdej jednostce czasu - nazywanej ZIG ZAG ZIG w rozdziale 1), aby ułatwić dowód , którym definiujemy algorytm, używając podziałów 2at+1 (ZIG ZAG jest powtarzany a razy), gdzie

0-wy podział składa się tylko z jednego zestawu [n]={1,…,n}. Dla
definiujemy podział
,
gdzie używamy rejestrów umieszczonych w czasie t. Część podstawowa - nazywana wisienką - jest zestawem rejestrów przypisanych do węzła i jego dwóch (prawdopodobnie pustych) podwęzłów.
składa się z tych części, dla starszego węzła na parzystych węzłach drzewa.
ma części z seniorem na nieparzystych węzłach.
jest identyczny jak
albo
zgodnie z identycznością i. (Kiedy węzły-seniory są na nieparzystych poziomach, węzły przypisane do źródła, które nie mają seniora, same tworzą swój zestaw.)

Kiedy rejestry zostaną przypisane do szczególnego węzła, tworzą co najwyżej dwa przedziały, części na górze składają się z co najwyżej sześciu przedziałów, ale łączą się ze sobą, tworząc co najwyżej trzy. Dlatego, ten podział może być jasno opisany, bez odwoływania się do struktury drzewa, jak to zostanie zrobione w następnym rozdziale. Jednakże, struktura drzewa pokazuje, dlaczego ten algorytm działa:

Dwa przedziały węzła-seniora otacza zestawy rejestrów z dwóch młodszych węzłów. Kiedy zastosujemy ε-sortowanie do tych rejestrów (do seniora i dwóch młodszych), zawartości, które są różnymi elementami - zbyt wielkimi lub zbyt małymi - zostają przeniesione do krawędzi, w górę do węzła-seniora. W wyniku tego, w kroku Bookkeeping elementy przemieszczają się w dół z rejestrami, ale w krokach ε-sortowania większość ze „zagubionych” elementów wędruje w górę po drzewie, i dlatego mają szansę znaleźć swoje właściwe miejsce w czasie 0(logn).

Innymi słowy, mamy poprawny mechanizm dla błędów ε popełnianych w każdym kroku, tak, żeby wykluczyć ich kumulowanie się.

Zbyt formalny opis

Mając algorytm ε-sortujący, można opisać sieć sortującą bezpośrednio, bez zagłębiania się w strukturę drzewa. (Jest to niestety ciężkie do zrozumienia).

Dla danego t definiujemy dwa podziały rejestrów 1,2,…,n.

Definiujemy zestaw
następująco:

Dla
,
,
składa się z następujących trzech przedziałów (dla definicji
przeczytaj rozdział 5.)

Jeśli j jest nieparzyste, a

Jeśli j jest parzyste.

Dla i=t-1 lub t,
,
zawiera jeden przedział.

jeśli j jest nieparzyste

jeśli j jest parzyste

Definiujemy również
jako połączenie dwóch przedziałów
oraz
.

Teraz podział
składa się z parzystych zestawów
, i=0,1,…,
,
kiedy podział
składa się z
i nieparzyste zestawy

,
.

Dane są dwa podziały, cykl t algorytmu zawiera zastosowanie ε-sortowania równocześnie w części
(krok ZIG) i potem tak samo dla
(krok ZAG) i powtarzać czynność naprzemiennie dla
i
przez cały czas.

Cały algorytm zaczyna się od zaaplikowania ε-sortowania dla całego zestawu rejestrów 1,2,…,n, wtedy cykl-t został przygotowany na t=1,2,…,logn.

Dowód

Notacja. Wszystkie rejestry i zawartości są zidentyfikowane numerami 1,…,n. Piszemy R(i)=j, jeśli zawartość rejestru i wynosi j, oraz R(i) oznacza
. Stłumimy czas w notacjach i rozwiążemy brakujące notacyjne problemy werbalnie.

Nazwa „przedział” i litery J, K będą używane dla wszystkich przedziałów zdefiniowanych w rozdziale 5 (tam nazywanych
). Przedział J formuje podział (1,…,n); J' będzie oznaczał następny przedział po prawej od J. Niższa część L(J) składa się z wszystkich przedziałów nie przekraczających J. Słowa „niższa część” zawsze oznacza L(J) dla niektórych przedziałów J. Definicja „wyższej części” jest podobna.

Dla przedziałów J i niższej części L=L(K), K<J, K'
, definiujemy dystans d(J, L), jako dystans dzielący dwa węzły, oznaczone jako J i K na drzewie. (Podobna definicja dla górnej części U). Zauważ, że d może równać się 0, jeżeli J i K znajdują się na tym samym węźle.

Definiujemy numery
jako proporcja elementów znajdujących się w rejestrze J, które zostały źle umieszczone z r lub więcej. Bardziej precyzyjnie, dla danego J i r
0, znajdziemy
dla każdego przedziału K, K<J, K'
J,
oraz
dla każdego przedziału K, K>J, K
J',
. Wtedy
jest definiowane jako:

(Kiedy sup jest brany jako pusty zestaw, definiujemy to jako 0.)

Ustalamy także:

Przez cały dowód zakładamy, że
jest mała (A jest duże), i ε jest wystarczająco mały w kategorii
(w rzeczywistości ε jest mniejszą potęgą
).

Idea kryjąca się za dowodem jest taka, że każdy krok algorytmu (ε-sortowanie ze wszystkimi częściami dzielenia) elementów (zawartości) nie znajdują się na prawym węźle drzewa , ale wszystkie przemieszczają się w prawym kierunku - z wyjątkiem nieistotnych proporcji.

Podążające za tym teorie, jasno mówią, że algorytm sortuje (w czasie logn nie ma błędów dopóki
.)

Teoria. Po każdym kompletnym cyklu, otrzymujemy:

Dowód. Wprowadzimy indukcję w czasie t. Dla t=0,
. Twierdzenie zgadza się dla niektórych t i udowadnia to dla t+1. Cykl rozpoczyna się zmianą wyznaczników rejestrów, dlatego redefiniujemy przedziały, sekcje,
. Następujące kroki algorytmu zwiększą jego liczbę błędów.

Lemat1. Jeśli
są błędami zanim rejestry zostaną wyznaczone, wtedy dla odpowiadających sobie numerów
, po wyznaczeniu otrzymamy estymaty:

Pokażemy teraz, że krok ZIG (albo ZAG) nie mogą utworzyć zbyt wielkiego błędu, dopóki kombinacja kroków ZIG ZAG je skutecznie zmniejsza.

Lemat2. Niech
będą błędami przed krokiem ZIG (albo ZAG), a
po tym kroku. Jeśli
, wtedy

Lemat3. Jeśli
, wtedy kroki ZIG ZAG zmienią błąd następująco:

Począwszy od hipotezy indukcyjnej, lemat 1 i powtarzające się wnioski z lematu 3 wykazują
że po nowym cyklu błędy
są tak małe jak potrzebujemy. Jednakże wydaje się, że błąd
wzrósł przez wszystkie kroki. To nie jest tak, o czym świadczy następujący lemat.

Lemat 4. Po kompletnym cyklu, otrzymujemy:

Pozostaje udowodnienie lematów.

Dowód lematu 1. Nowy przedział J' jest połączeniem, co najwyżej trzech segmentów, z których każdy zawiera się w starym przedziale J, i
dla każdego z nich. Taki segment przesuwa się co najwyżej 2 poziomy na drzewie. Podobnie, nowa sekcja L'(K) jest zawarta w starej części L(K) i K' jest co najwyżej 2 poziomy dalej od K na drzewie. Stąd lemat wynika.

Dowód lematu 2. Używamy słowa `pobliskie', jeśli odnosimy się do odległości na drzewie i zamykamy na odległość realną. Większość elementów należących do L będzie przesunięta do lewej, i będzie przemieszczać się do L lub do najbliższego przedziału. Numery elementów nie mogą przekroczyć części wiśni, co stanowi mniej niż
części każdego przedziału wiśni. Ponieważ zamknięty przedział jest (jednym z) najbliższych, wielkość błędu nie wzrośnie, z wyjątkiem co najwyżej proporcji powyżej
, gdzie może wzrosnąć co najwyżej o dwa. Niektóre elementy L mogły wyjść poza zakres L, ale one po prostu zamieniły się z elementami już należącymi do L, nie zmieniając ich liczby.

Dowód lematu 3. Jedyną dodatkową uwagą, jaką potrzebujemy, jest, że jeśli mamy przedział J,
, to był najbliżej L (poza L) w etapie ZIG, a następnie nie będzie najbliższy w kroku ZAG. Tak więc, nie tylko, że błędy, nie będą rosnąć (z wyjątkiem niewielkiej części), ale będą ściśle spadać.

Uwaga. Zawsze zakłada się, że
, by zapewnić, że skrajny przedział wisienki (co stanowi około
części całej wisienki), może pomieścić wszystkie elementy zewnętrzne. Ale ten ekstremalny przedział może być pusty. Jednakże całkowita liczba rejestrów wisienki jest mniejsza niż 4A, i
, tzn. wszystkie rejestry wiśni zawierają własne elementy (R(i)=i).

Dowód lematu 4. Rozważamy przedział J, i oszacowujemy liczbę
. Jest z pewnością ograniczona przez liczbę
, co jest oczywiście równe
. Równość y=z skutkuje dla liczb
i
, a równanie:

Teraz szacujemy części po prawej stronie, bo ze względu na symetrię, wystarczy pracować na
i
. Widać wyraźnie, że
, trudniejszym zadaniem jest oszacowanie
.

Mamy podział L(J)-J w przedziałach. Możemy mieć przedział
, który jest w
odległości 0 od J'. Dla tego
:

Liczba przedziałów tego podziału, które są w odległości r>1 od J' wynosi co najwyżej
, a ich wielkość wynosi co najwyżej
. W ten sposób:

Pokazaliśmy już, że
jest niewielkie. Zakładamy, że przedziały J i J' są na tej samej
wisience dla kroku ZIG (jeśli nie są one na tej samej wisience, ani w ZIG, ani w ZAG, należą do różnych elementów, a my stwierdziliśmy już, że w tym przypadku
). Jeśli ograniczenie z prawej strony (4) jest mniejsze niż
, po kroku ZAG, a następnie krok ZIG będzie wymieniać wszystkie elementy zewnętrzne J i J' z wyjątkiem co najwyżej

Automatycznie użyliśmy przekształceń trywialnych.

Lemat 5. Dla jakiegokolwiek k,
, numery
oraz
monotonnie zmieniają algorytm na malejący.

(Jest to prawda dla wszystkich sieci porównawczych, gdzie zamiana polega na umieszczeniu elementu większego do większego rejestru.)

---