Informatyka MIMUW

Słabością algorytmu MergeSort jest pomocnicza tablica używana do scalania. Czy można jej się pozbyć? Tak, można to zrobić na dwa sposoby. Pierwszy sposób polega na wykonywaniu scaleń w miejscu, czyli w samej tablicy \( a \). Niestety liczba porównań i przemieszczeń elementów znacząco rośnie, choć jest nadal liniowa. Sam algorytm nie jest intuicyjny i pominiemy go w tych notatkach. Drugi sposób polega na wykonaniu sortowania przez scalanie przy złamaniu zasady, że długości scalanych ciągów różnią się co najwyżej o 1. Z opisanej procedury Merge-1 wynika, że scalanie dwóch ciągów możemy wykonać w taki sposób, żeby długość pomocniczej tablicy była równa długości krótszego ze scalanych ciągów. Rozważmy teraz procedurę \( Merge-2(p,r,s) \), która scala uporządkowane ciągi \( a[p..s] \) z \( a[s+1..r] \). Zakładamy przy tym, że \( s-p+1 \le r-s \) (lewy ciąg jest nie dłuższy niż prawy) oraz \( p-1 \ge s-p+1 \) (początek tablicy jest wystarczająco długi, żeby można go wykorzystać do scalania). Scalanie będzie się odbywało z pomocą podtablicy \( a[1..p-1] \). Będziemy przy tym uważali, żeby nie zgubić zawartości tej podtablicy. Oto nasza procedura \( Merge-2(p,r,s) \).

Algorytm Scalanie-2

  procedure Merge-2(p,r,s); 
  begin
    //zamiana a[p..s] z a[1..s-p+1]  
    for i := p to s do 
      Exchange(i-p+1,i); 
    //właściwe scalanie 
    i := 1; j := s+1; k := p-1;  
    while (i <= s-p+1) and (j <= r)do 
    //Niezmiennik: a[p..k] - scalone podciągi a[1..i-1], a[s+1..j-1]  
    begin
      k := k+1;  
      if a[i] <= a[j]  then 
        begin Exchange(i,k); i := i+1 end 
      else 
        begin Exchange(k,j); j := j+1 end 
  end; 
  //jeśli nie wyczerpaliśmy ciągu  a[1..s-p+1], 
  //to przepisujemy go na koniec tablicy a 
  for j := i  to s-p+1 do 
  begin k := k+1; Exchange(j,k) end 
end;

Zauważmy, że po wykonaniu powyższego algorytmu mamy następującą sytuację:

- podtablica \( a[1..p-1] \) zawiera te same elementy, które znajdowały się w niej przed rozpoczęciem scalania (być może przepermutowane),

- podtablica \( a[p..r] \) jest już uporządkowana.

Oznaczmy przez MergeSortBis(p,r) procedurę, która sortuje przez scalanie podtablicę \( a[p..r] \). Załóżmy przy tym, że \( p-1 \ge \frac{r-p+1}{2} \). Procedurę MergeSortBis implementujemy podobnie jak algorytm MergeSort, tylko zamiast procedury Merge-1 wykorzystujemy procedurę \( Merge-2 \). Możemy teraz opisać algorytm "sortowania przez scalanie w miejscu". Idea algorytmu jest następująca. Dzielimy tablicę \( a \) na dwie (prawie) równe części \( a[1..\lceil \frac{n}{2} \rceil] \) oraz \( a[\lceil \frac{n}{2} \rceil + 1..n] \). Sortujemy prawą część tablicy algorytmem \( MergeSortBis \) wykorzystując lewą część jako tablicę pomocniczą. Dalsza część algorytmu ma strukturę rekurencyjną. Załóżmy, że w tablicy \( a \) mamy już posortowany sufiks \( a[p..n] \) dla pewnego \( 1 < p\le \lceil \frac{n}{2} \rceil + 1 \). Jeśli \( p-1 = 1 \), to kończymy sortowanie wstawiając \( a[1] \) do uporządkowanego ciągu \( a[2..n] \), tak jak w sortowaniu przez wstawianie. Jeśli \( p > 2 \), wówczas dzielimy tablicę \( a[1..p-1] \) na podtablicę \( a[1..\lceil \frac{p-1}{2}\rceil] \) i \( a[\lceil \frac{p-1}{2}\rceil + 1..p-1] \), sortujemy przez scalanie podtablicę \( a[\lceil \frac{p-1}{2}\rceil + 1..p-1] \), scalamy uporządkowaną podtablicę \( a[\lceil \frac{p-1}{2}\rceil + 1..p-1] \) z podtablicą \( a[p..n] \) i sortujemy dalej rekurencyjnie przy założeniu, że \( a[\lceil \frac{p-1}{2}\rceil + 1..n] \) jest już posortowane.

Algorytm sortowania przez scalanie w miejscu można teraz zapisać następująco.

Algorytm SortowaniePrzezScalanie w Miejscu

  if n > 1 then 
  begin 
    p := n - floor(n/2)  + 1; 
    MergeSortBis(p,n); 
    while  p > 2 do 
    begin 
      l := p - floor((p-1)/2) +1;  
      MergeSortBis(l,p-1); 
      Merge-2(l,n,p-1); 
      p := l 
    end; 
    Scal a[1] z  a[2..n]. 
end

Zastanówmy się teraz nad złożnością przedstawionego algorytmu. Zanalizujemy najpierw liczbę porównań. Odzielnie analizujemy porównania wykonywane dla sortowania procedurą \( MergeSortBis \), a oddzielnie dla scaleń procedurą \( Merge-2 \). \( MergeSortBis \) jest wywoływana dla ciągów o długościach \( \lfloor \frac{n}{2} \rfloor, \lfloor \frac{n}{4} \rfloor, \ldots \). Jeżeli sortowanie ciągu długości \( k \) wymaga co najwyżej \( k\log k \) porównań, to liczba porównań we wszystkich sortowaniach wynosi co najwyżej

Na koniec zauważmy jedno drobne "oszustwo". Procedura \( MergeSort \) i wzorowana na niej procedura \( MergeSortBis \) są procedurami rekurencyjnymi. Implementacja rekursji wymaga stosu, w tym przypadku o logarytmicznej wysokości. Żeby mieć w pełni algorytm sortowania w miejscu, powinniśmy pozbyć się stosu. W przypadku zwykłego sortowania przez scalanie, a takie jest zaimplementowane w \( MergeSortBis \), bardzo łatwo z góry ustalić, kiedy i które podtablice są ze sobą scalane. Załóżmy, że sortujemy przez scalanie procedurą \( MergeSort \) tablicę o długości \( 2^k \), dla pewnego \( k > 0 \). Zauważmy, że w takim przypadku scalamy najpierw podtablice jednoelementowe \( a[1] \) z \( a[2] \), \( a[3] \) z \( a[4] \), itd., potem podtablice dwuelementowe \( a[1..2] \) z \( a[3..4] \), \( a[5..6] \) z \( a[7..8] \), itd., a na koniec podtablicę \( a[1..2^{k-1}] \) z \( a[2^{k-1}+1..2^k] \). Łatwo zaimplementować taki ciąg scaleń za pomocą iteracji. Szczegóły tej implementacji i jej uogólnienie na tablice o długościach różnych od potęg dwójki, pozostawiamy jako dobre ćwiczenie algorytmiczno-programistyczne.