Sortowanie przez scalanie

Sortowanie przez scalanie (ang. mergesort) jest jedną z szybszych metod sortowania. Algorytm działa w złożoności $O(n log(n))$ gdzie $n$ odpowiada liczbie elementów w tablicy. Korzysta z rekurencji.

Sam algorytm przedstawia się w następujący sposób:

1. Podziel tablicę na dwie części.
2. Wywołaj procedurę sortowania przez scalanie dla obu części.
3. Scal obie części.

Scalanie polega na wprowadzaniu liczb równolegle z obu części do tablicy docelowej.

Algorytm

 procedure mergesort ( tab : tablica, p : początek tablicy, k : koniec tablicy )
    if k == p then
      return
    end if
    
    if p + 1 == k and p > k then
      swap (tab [k], tab [p]);
    end if
    
    n = p + k / 2
    mergesort ( tab, p, n )
    mergesort ( tab, n + 1, k )
    
    pomocnicza : tablica pomocnicza
    
    for (iA = p, iB = n + 1, iP = 0; iP < wielkość_tablicy (pomocnicza); iP++) do
      if (iA <= n and iB <= k) then
        if (tab [iA] <= tab [iB]) then
          pomocnicza [iP] = tab [iA]
        else
          pomocnicza [iP] = tab [iB]
        end if
      else if (iA <= n) then
        pomocnicza [iP] = tab [iA]
      else if (iB <= k) then
        pomocnicza [iP] = tab [iB]
      end if
   end
   
   skopiuj tablicę pomocnicza na miejsca tablicy tab
 end procedure