Algorytmy i struktury danych/Wstęp: elementarne techniki algorytmiczne i struktury danych

Podstawowe techniki i struktury

Nie ma formalnej teorii ani gotowych "recept" na konstrukcję efektywnych algorytmów. Opiszemy nieformalnie kilka podstawowych technik. Niektóre z nich są wstępnie omawiane na kursie metod programowania. Tutaj rozważymy je przede wszystkim w aspekcie złożoności obliczeniowej i analizy algorytmów.

Metoda dziel i zwyciężaj

które rozwiązujemy niezależnie, następnie scalamy rozwiązania podproblemów. Metoda działa dobrze gdy scalanie podproblemów jest łatwe, oraz podproblemy są małe w stosunku do $n$.

Jako przykład rozważmy jeszcze raz problem liczenia przywódcy tablicy (patrz Moduł 1). Stosując metodą dziel i zwyciężaj możemy otrzymać następujący algorytm:

\myskip

\noindent \hspace*{1cm} Algorytm Rekurencyjny-Przywódca;\\

   \hspace*{1cm} if n=1 then przywódcą jest pojedyńczy element tablicy\\

\hspace*{1cm}

   else\\
\hspace*{1.4cm}   podziel tablicę na dwie połowy;\\
\hspace*{1.4cm}   rekurencyjnie oblicz przywódcę lewej i prawej połowy tablicy;\\
 \hspace*{1.4cm}  sprawdź w czasie O(n) który z nich jest przywódcą całości;

\myskip

\noindent Jeśli algorytm ten wykonuje  $T(n)$ kroków to:

\centerline{$T(n)=2\cdot T(n/2)+O(n),T(1)=1$} \vskip 0.2cm

\noindent Rozwiązaniem jest $T(n)=O(n\log n)$  (jak

wiadomo z kursu matematyki dyskretnej).

Metoda zachłanna

minimalizujemy pewną wartość. Algorytm w każdej iteracji ma do wyboru pewną liczbę lokalnych akcji. W przypadku maksymalizacji wybiera tę, która lokalnie maksymalizuje wartość docelową, w przypadku minimalizacji wybiera akcję o minimalnej wartości. Przedyskutujemy tę metodę na następujących dwóch pzykładach. \paragraphWieże na szachownicy. Przypuśćmy, że mamy szachownicę n na n, na polu (i,j)-tym leży x(i,j) monet. Chcemy umieŚciĆ n wież na szachownicy tak aby żadne dwie się nie biły. Zyskiem jest suma monet na wybranych pozycjach. Lokalna akcje to wybranie jednej dopuszczalnej pozycji (tzn. takiej, że wieża umieszczona na tej pozycji nie bije żadnej wieży umieszczonej dotychczas. Zysk akcji to liczba monet na pozycji. Algorytm zachłanny działa trywialnie: wybieramy pozycję z maksymalnym x(i,j). Łatwo widać, ę ten algorytm niekoniecznie da optymalny zysk, ale da co najmniej połowę optymalnego zysku. Pozostawiamy to jako ćwiczenie. Bardziej formalnie można wyrazić ten problem w terminach skojarzeń w grafach. Najciekawszym przypadkiem jest sytuacja, gdy tablica x(i,j) jest zero-jedynkowa.

Przejdziemy teraz do wersji minimalizacyjnej. \paragraphMinimalne Sklejanie Par.

Przypuśćmy, że mamy ciąg $n$ nieujemnych liczb $p_1,p_2,\dots ,p_n$. Lokalna akcja sklejania polega na

pobraniu dwóch elementów z ciągu i zastąpieniu ich przez sumę ich wartości, kosztem akcji jest suma wartości sklejanych elemenów. Ciąg operacji sklejania kończy się gdy skleiliśmy wszystko do jednej wartości.

Interesuje nas policzenie minimalnego sumarycznego kosztu sklejania $n$ elementów w jeden element. Metoda zachłanna zawsze wybiera akcję o minimalnej wartości. \vskip 0.3cm \noindent \myskip \hspace*{1cm}

Algorytm Schemat-Zachłanny;

\hspace*{1cm}
     while zbior mozliwych lokalnych akcji jest niepusty do\\
              \hspace*{1.9 cm} wykonaj akcję o minimalnym koszcie;

     \hspace*{1cm} return (suma kosztow wykonanych akcji)

\vskip 0.3cm \noindent

Można to zapisać bardziej formalnie:
\myskip \hspace*{1cm}
Algorytm Optymalne-Sklejanie-Par;
%\hspace*{1cm} $/*$  Zastosowanie metody zachłannej $*/$

\hspace*{1cm} $wynik:=0$;

 \hspace*{1cm} {\bf while} mamy co najmniej dwa elementy do

  \hspace*{1.5cm} zastąp dwa minimalne elementy $a,b$ przez $a+b$

   \hspace*{1.5cm} wynik := wynik + a+b;

\myskip Pozostawiamy jako ćwiczenie dowód tego, że algorytm ten daje minimalny ciąg sklejeń. Co będzie, jeśli zamiast liczyć minimalny koszt chcielibyśmy policzyć ciąg, który maksymalizuje sumaryczną sumę kosztów $a+b$ ? Pozostawiamy to jako ćwiczenie. \myskip W naszym przykładzie mogliśmy sklejać elementy, które niekoniecznie są sąsiednie, kolejność elementów w ciągu nie odgrywała roli. Zastanówmy się co będzie gdy wprowadzimy do gry kolejność elementów. Załóżmy teraz, że możemy sklejajać tylko elementy sąsiednie. Tak zmodyfikowany problem nazwijmy problemem Minimalego Sklejania Sąsiadów. Możemy w poprzednim algorytmie zastąpić zwrot dwa minimalne elementy przez dwa sąsiednie elementy o minimalnej sumie. Niespodziewanie, nasz algorytm nie zawsze liczy minimalną wartość, czyli nie jest poprawny.

Programowanie dynamiczne

Algorytm Optymalne-Sklejanie-Sąsiadów;

\hspace*{1cm} for each $i$ $wynik[i,i]:=0$;

\hspace*{1cm} for $i:=1$ to $n$ do\\

 \hspace*{2cm} for $j:=i+1$ to $n$ do\\
  \hspace*{2.3cm} $wynik[i,j]$ := $\underset{i\le k<j}{\min }wynik[i,k]+wynik[k+1,j]+{\sigma }_{i,j}$

  \hspace*{1cm} return wynik[1,n];

\myskip Algorytm ma złożoność czasową $O(n^3)$ i jest to typowa złożoność algorytmów tego typu. Duża złożoność wynika stąd że liczymy wartości dla mnóstwa podproblemów, które mogą być zupełnie nieistotne ze względu na optymalne rozwiązanie. \myskip Dygresja.\ Problem sklejania sąsiadów można rozwiązać inaczej, modyfikując w sposób nietrywialny algorytm Optymalne-Sklejanie-Par.

W algorytmie tym instrukcję

zastąp dwa minimalne elementy $a,b$ przez $a+b$

\noindent zamieńmy na:

zastąp dwa sąsiednie elementy $a,b$ o minimalnej sumie przez $a+b$;\\ \hspace*{0.5cm} przesuń $a+b$ przed najbliższy na prawo (w ciągu) element $c$ większy od $a+b$\\ \hspace*{0.5cm} ewentualnie na koniec ciągu, jeśli takiego $c$ nie ma. \myskip Otrzymany algorytm, wersja algorytmu Garsia-Wachsa, liczy koszt minimalnego sklejania sąsiadów. Jest to przykład pozornie prostego algorytmu, dla którego odpowiedź na pytanie dlaczego to działa jest niezwykle skomplikowana i wykracza poza zakres tego kursu. Pozostawiamy jako ćwiczenie implementację tego algorytmu w czasie $O(n\log n)$ zakładając, że jest on poprawny. Jeśli liczby $p_i$ są liczbami naturlnymi z przedziału $[1..n]$ to istneiej nawet (bardzo trudna) implementacja w czasie liniowym.

Konstruowanie algorytmu metodą transformacji

Algorytm efektywny otrzymujemy często startując od prostszego, ale mało efektywnego algorytmu. Następnie staramy się, za pomocą prostych transformacji, przekształcić prosty algorytm w algorytm docelowy. Można to równieź nazwać stosowaniem metody kolejnych przybliżeń w aspekcie inżynierii algorytmicznej. Większość prostych algorytmów z Modułu 1 można potraktować jako produkty transformacji algorytmów naiwnych. Pozostawiamy jako ćwiczenie pokazanie tego. Pokażemy jedynie prosty przykład obliczania liczby inwersji \paragraph{Liczba inwersji.}\ Mamy dane dwie posortowane rosnąco tablice $A[1..n],B[1..n]$, mamy policzyć liczbę par $i,j$ takich, że $A[i]>B[j]$. Jeśli $A[1..n],B[1..n]$ są posortowanymi rosnąco tablicami, to liczbę inwersji między A, B oblicza następujący naiwny algorytm.

\myskip
       \hspace*{1.5cm} Algorytm Liczba-Inwersji-Naiwnie;
       \begin{verbatim}
        wynik := 0;
        for i := 1 to n do
           j := 0;
           while (j<n and A[i]>B[j+1]) j := j+1;
           wynik := wynik + j;

\end{verbatim} \myskip Algorytm ma złożoność kwadratową. Załóżmy, że początkową wartością j jest zero. Wtedy, przyglądając się dokładniej algorytmowi, widzimy że instrukcję j := 0; można usunąć bez szkody dla poprawności i złożoność stanie się liniowa. Pozostawiamy to jako ćwiczenie. W ten sposób mamy prostą transformację kwadratowego algorytmu naiwnego na algorytm liniowy. \myskip Przykład ten był dosyć ubogi i

przedyskutujemy jezcze bardziej skomplikowany przykład.
Podamy

przykład transformacji pewnego prostego algorytmu B(n) w nietrywialny algorytm $A_n$, transformacja ta bazuje na własnościach B(n). Kluczem do efektywnej transformacji jest analiza własności algorytmu B(n). \paragraphWykrywanie fałszywej monety. Mamy zbiór monet o numerach 1,2,..,N, wszystkie o tej samej wadze, wiemy że wsśród nich jest dokładnie jedna fałszywa moneta o innej wadze. Modelem algorytmu jest ciąg ważeń na wadze szalkowej. Niech waga(A) oznacza sume wag monet ze zbioru A. W jednym wazeniu mozemy wykonac operacje Por"wnaj(A,B), gdzie A,B sa rozlacznymi podzbiorami 1,2,..,N. Otrzymujemy jedną z trzech możliwych odpowiedzi: \vskip 0.3cm

  L\ -\ gdy $waga(A)<waga(B)$,\ \
  P\ -\ gdy $waga(A)>waga(B)$,\ \
  R\ -\  gdy wagi sa równe.

\vskip 0.3cm \noindent

Algorytmem w naszym modelu jest ciąg operacji $o{p}_1,o{p}_2,...,o{p}_n$ taki, że  z otrzymanego

ciagu opdpowedzi można jednoznacznie wyznaczyc fałszywą monetę i określić czy jest ona cięższa czy lżejsza niż inne. Operację Porównaj(A,B)będziemy w skrócie zapisywać jako parę (A,B). Nasz algorytm można zatem zapisać jako ciąg par rozłacznych zbiorów, na przykład: {Parser nie mógł rozpoznać (błąd składni): {\displaystyle %Przykład: % \noindent \begin{verbatim} Algorytm dla n=2, N=3: ({1}, {2}), ({1}, {3}). Algorytm dla n=3, N=12: ({1,2,3,10},{4,5,6,11}), ({1,2,3,11},{7,8,9,10}), ({1,4,7,11},{2,5,8,12}) \end{verbatim} % Naszym głównym zadaniem jest dla danego n znalezienie algorytmu ważeń, który maksymalizuje N. \noindent Pokażemy najpierw jak rozwiązać zadanie dla $N=3^{n-1}$. Załóżmy, że liczba monet jest poteęgą trójki i monety są ponumerowane $0,1,2.. 3^{n}-1$. Niech S(k,0), S(k,1) oznaczają zbiory numerów monet, które na k-tym bicie (licząc od końca) w reprezentacji trójkowej mają odpowiednio 0, 1. GdybyŚmy wiedzieli od razu czy fałszywa moneta jest lżejsza czy cięższa, to mamy następujący prosty algorytm, który działa podobnie jak wyszukiwanie ternarne: } } {Parser nie mógł rozpoznać (błąd składni): {\displaystyle % Ponieważ nie znamy statusu fałszywej monety dodajemy jedno porównanie i otrzymujemy algorytm B(n) który obsługuje za pomocą n ważeń $N = 3^{n-1}$ monet (mamy teraz tylko n-1 bitów ternarnych). % } } zięki dodaniu na początku jenego ważenia już po pierwszych dwóch ważeniach już wiemy jaki jest status fałszywej monety (lżejsza, cięższa). Poza tym wynikiem pierwszych dwóch ważeń nie może być LR ani RL. Te dwie własności algorytmu B(n) są kluczem do transformacji tego algorytmu w algorytm $A_n$.

Jeśli mamy w naszym modelu algorytmy $A1(n)=(A_1,B_1),(A_2,B_2)...(A_n,B_n)$ oraz A2(n) = (C_1,D_1),(C_2,D_2)...(C_{n},D_{n})$, to definiujemy algorytm {Parser nie mógł rozpoznać (błąd składni): {\displaystyle Załóżmy, że mamy algorytm $A_{n-1}\ =\ (A_1,B_1),(A_2,B_2)...(A_{n-1},B_{n-1})$ na zbiorze rozmiaru $N_{n-1}$ to oznaczmy przez $przeskaluj(A_{n-1})$ algorytm, który działa na zmodyfikownych numerach monet, do każdego numeru dodajemy $3^{n-1}$. Ponadto dodajemy jedno porównanie: } } Docelowy algorytm definiujemy rekurencyjnie: {Parser nie mógł rozpoznać (nieznana funkcja „\noindent”): {\displaystyle \noindent Poprawność takiej konstrukcji wynika stąd że na podstawie wyników 2 pierwszych ważeń wiemy, czy fałszywa moneta jest mniejsza od $3^{n-1}$. Jeśli tak to traktujemy odpowedzi jak w B(n), jesli nie to jak w A(n-1). Zostawiamy jako ćwiczenie opisanie sposobu takiego przełączania się. W ten sposób mamy algorytym, który za pomocą n ważeń obsługuje $N_n$ monet, gdzie } } Dla n = 2,3,4,5,6,7 mamy: $

N_n\ =\ 3,\ 12,\ 39,\ 117,\ 351,\ 1053\ldots$

\noindent
Dygresja: teoretycznie interesujące w tym jest to, że są to maksymalne  wartości N.
Pozostawiamy dowód jako ćwiczenie. Istnieją różne optymalne algorytmy dla tego problemu.

Znaczenie struktury danych

Podstawową strukturą danych jest struktura obsługująca operacje delete(S), insert(x,S), dla zadanego zbioru S. Operacja delete pobiera z S i zwraca jako wartość pewien element S. Nie interesuje nas na razie który element zostanie usunęty. Niedeterminizm pozwala nam użyć w takim wypadku jednej z kilku struktur danych które dyskutujemy poniżej. W niektórych zastosowaniach istotne jest który element jest pobierany i wtedy nazwy operacji insert, delete często zmieniamy na nazwy bardziej odpowiadające terminologicznie tym strukturom, ale będziemy też używć nazewnictwa delete, insert, o ile nie prowadzi to do niejednoznaczności. Elementarne struktury danych w których zdeterminowane są operacje insert, delete to:\ lista, stos, kolejka. Są one punktem wyjścia do bardziej skomplikowanych struktur.

\noindent W następujących dwóch przykądach możemy sobie pozwolić na niedeterministyczny wariant operacji delete. \myskip Maksymalna bijekcja. Przypuśćmy, że mamy funkcję $f\ :\ \{1,2,\ldots n\} \rightarrow \{1,2,\ldots n\}Parser nie mógł rozpoznać (błąd składni): {\displaystyle , zadaną tablicą } f[1..n] i chcemy znaleźć rozmiar maksymalnego podzbioru, na którym ta funkcja jest bijekcją. \myskip Dwie funkcje. Jest to zadanie bardzo podobne, mamy dwie funkcje $f_1,f2$ ze zbioru $[1..n]$ w siebie. Chcemy znaleźć taką permutację $\pi =(i_1,i_2,\dots i_n$, żeby $\pi (f_k(i))>\pi (i),\mathrm{\forall }1\le i\le n,k=1,2$ Oba te przykłady możemy wyrazić w terminach teorii grafów. Zakładamy, że czytelnik dowiedział się na matematyce dyskretnej co to jest graf. Zbiorem wierzachołków jest tutaj zbiór $[1..n]$. W pierwszym przykładzie krawędzie są postaci $(i,f(i))$, w drugim postaci $(i,f_k(i)$, gdzie $k=1,2$. W pierwszym przykładzie chcemy znaleźć maksymalny podzbiór grafu, na którym podgraf indukowany jest zbiorem cykli. W drugim przypadku mamy szczególną instancję tzw. sortowania topologicznego grafu. WIerzchołek nazywamy roboczym, gdy nie wchodzi do niego żadna krawę"dź.

Niech $S$ będzie początkowo zbiorem wszystkich wierzchołków roboczych. Algorytmy dla obu powyższych problemów działają w podobny sposób. Pobieramy element $v\in S$, odpowiednio przetwarzamy $v$, i usuwamy $v$ z grafu. Wskutek usunięcia pewne nowe wierzchołki stają się roboczymi i wstawiamy je do S. Kontynuujemy, dopóki S jest niepusty.

W przypadku problemu maksymalnej bijekcji po prostu usuwamy v, w przypadku numeracji $\pi$, $\pi (v)$ staje się kolejnym numerem. Pomimo interpretacji grafowej nie musimy implementować żadnej reprezentacji grafu, wszystko się dzieje w wejściowych tablicach i w dodatkowej tablicy licznik[v], w której trzymamy dla każdego $v$ ile jest krawędzi aktualnie wchodzących do v. Konkretną implementację pozostawiamy jako ćwiczenie. Zbiór S jest tutaj zbiorem wierzcho"ków roboczych, które są w pewnym sensie akcjami do wykonania. Do S wkładamy akcje które mamy wykonać, kolejność nie jest istotna. S może być listĄ, stosem lub kolejką.

\myskip Pokażemy jeszcze jeden ciekawy problem dla którego właśnie lista jest świetną strukturą

danych. \myskip Panorama Warszawy. Rozważmy inny przykład algorytmu, ktorego złożoność istotnie zależy od (bardzo prostej) struktury danych. Przypuśćmy, że mamy na wejściu $n$ trójek postaci $[p,q,s]$, gdzie p,q \in \{1,2,\ldots,n\}$,$s\ge 0Parser nie mógł rozpoznać (błąd składni): {\displaystyle . Każdej trójce odpowiada funkcja } f_{p,q,s} taka, że:

$f_{p,q,s}(i)=s$ gdy $p\le i\le q$, oraz $f_{p,q,s}(i)=0$ w przeciwnym przypadku.

\noindent Naszym zadaniem jest dla każdego $1\le i\le n$ obliczyć wartość $F(i)$, będącą maksimum z danych funkcji $f_{p,q,s}$ dla argumentu $i$. Można podać następującą interpretację. Każda funkcja $f_{p,q,s}$ opisuje kształt wieżowca w Warszawie patrząc z prawej strony Wisły. Wtedy funkcja $F$ opisuje panoramę centrum Warszawy.

\noindent Załóżmy, że trójki $(p,q,s)$ są posortowane ze względu na $s$. Wtedy rozważamy kolejno funkcje $f_{p,q,s}$, w kolejności rosnącego $s$, i nadajemy za każdym razem końcowe wartości dla pozycji z przedziału $[p,q]$ dla których jeszcze wartości nie są policzone. Taki algorytm miałby złożoność kwadratową.

Jeśli użyjemy listy dwukierunkowej i za każdym razem usuniemy zbiór pozycji dla których wartości końcowe są już policzone to otrzymamy algorytm działający w czasie liniowym. Dokładny zapis algorytmu pozostawiamy czytelnikowi jako ćwiczenie. \myskip Wariantem kolejki jest kolejka priorytetowa, jest to struktura danych, która obsługuje ciąg operacji insert, delete, gdzie operacja delete zawsze pobiera minimalny element. Operację tę nazwiemy w tym przypadku ExtractMin. \myskip \noindent Pokażemy na przykładzie algorytmu Optymalne-Sklejanie-Par zastosowanie kolejki priorytetowej.

W algorytmie tym podstawowową operacją
jest:

\vskip 0.3cm

zastąp elementy $a,b$ przez $a+b$.

\vskip 0.3cm

\noindent Operacja ta jest równoważna operacjom:

\vskip 0.3cm

$a=ExtracMin(S)$; $b=ExtractMin(S)$; $Insert(a+b,S)$

\vskip 0.3cm

\noindent W dalszej części kursu pokażemy, jak każdą z operacji Insert, ExtractMin

zaimplemnetować w czasie logarytmicznym. W szczególnym przypadku, rozważonym poniżej, można je zaimplementować w czasie stałym. Załóżmy, ę początkowy zbiór $S$ jest posortowany i jego elementy są umieszczone na stosie $ST$ w kolejnoęsci rosnącej (od wierzchołka w dół). Załóżmy, że mamy dodatkowo zwykłą kolejkę $Q$ początkowo pustą. Wtedy ciąg operacji \vskip 0.3cm

$a=ExtracMin(S)$; $b=ExtractMin(S)$; $Insert(a+b,S)$

\vskip 0.3cm

\noindent możemy wykonać w czasie stałym: element minimalny jest na wierzchołu $ST$ lub na

początku kolejki $Q$, element $a+b$ wstawiamy na koniec $Q$. Zatem algorytm Optymalne-Sklejanie-Par mozemy zaimplementować w czasie liniowym gdy początkowy zbiór jest od razu posortowany. Widzimy na tym przykładzie w jaki sposób złożoność algorytm zależy od struktury danych związanych z algorytmem. \myskip Sortowanie kolejkowe i stosowe. Działanie stosu i kolejki świetnie ilustrują różne warianty problemu sortowania z użyciem stosów i kolejek. Niech $\pi$ będzie permutacją liczb $\{1,2,\dots n\}$. Możemy posortować $\pi$ stosując niedetrministyczny algorytm: \myskip

while na wyjściu nie są wszystkie elementy do

\noindent \hspace*{0.8cm} wstaw kolejny element $\pi (i)$ do jednej z kolejek \\ \hspace*{0.8cm} lub wypisz $\pi (i)$ na wyjściu \\ \hspace*{0.8cm} lub pobierz i wypisz na wyjściu pierwszy element jednej z kolejek \myskip Zdefiniujmy liczbę kolejkową permutacji $\pi$ jako minimalną liczbę kolejek potrzebnych do posortowania permutacji $\pi$. Na przykład dla $\pi =(1,2,3)$ liczba ta wynosi 0, a dla $\pi =(3,2,1)$ wynosi 2. Jak policzyć liczbę kolejkową w czasie liniowym ? Porównajmy ten problem z problemem maksymalnego malejącego podciągu. Pozostawiamy tojako ćwiczenie.

Podobnie definiujemy liczbę stosową, w tym wypadku w powyższym nieformalnym algorytmie

zastępujemy kolejkę przez stos. Można również zdefiniować liczbę kolejkowo-stosową, pytając o minimalną liczbę stosów i kolejek, które razem posortują daną permutację. Jest to trudne pytanie. \myskip W poprzedniej wersji sortowania każdy element może trafić tylko do jednej kolejki. Rozważmy teraz wersję w której mamy $k$ kolejek $Q_1,Q_2,Q_3,\dots Q_k$ i element może trafiać do kolejek o coraz mniejszych numerach. Pojedyńcza operacja polega na wstawieniu kolejnego elementu z $\pi$ do jednej z kolejek, wypisaniu bezpośrednio na wyjście o ile jest on pierwszym niepobranym elemntem w $\pi$ lub pierwszym elementem pewnej kolejki, lub przełożeniu pierwszego elementu pewnej kolejki $Q_i$ do kolejki $Q_j$, dla $j<i$. Można pokazać, że wystarczy logarytmiczna liczba kolejek do posortowania każdej permutacji.

Podobny fakt zachodzi, gdy kolejki zastąpimy stosami. Pozostawiamy ten problem (zrówno dla kolejek jak i stosów) jako ćwiczenie. \myskip Scalanie kolejkowe. Załóżmy, że każdy elemnet ciągu $\pi$ jest początkowo listą jednolelementową, oznaczmy zbiór tych list przez $S$. Załóżmy też, że umiemy scalić dwie posortowane listy w czasie równym sumie ich długości za pomocą operacji $merge$ (patrz następne wykłady). \myskip {\bf Algorytm} Scalanie-Kolejkowe;

while $|S|>1$ do

\hspace*{0.5cm}lista1 = delete(S); lista2 = delete(S);

\hspace*{0.5cm}insert(merge(lista1,lista2),S) \myskip Pozostawiamy jako ćwiczenie pokazanie tego, że algorytm ten działa w czasie $O(n\log n)$, a jeśli $S$ stanie się stosem to działa w czasie kwadratowym. Widać na tym przykładzie przewagę kolejki nad listą. Załóżmy, że mamy posortować tablicę $A[0,1,\dots ,n-1]$ i $n$ jest potęgą dwójki. Wtedy następujący algorytm wykonuje ten sam ciąg scaleń co algorytm Scalanie-Kolejkowe. Dowód tego pozostawiamy jako ćwiczenie.

\noindent \begin{verbatim} Algorytm Scalanie-Kolejkowe bez kolejki;

   m = 1;
   while m < n do
       for i=0 to n/(2m) do
           merge(A[i..i+m-1], A[i+m..i+2m-1]);
       m = 2m;
 \end{verbatim}