zadania z informatyki - Analiza algorytmów

Rozważmy następujący algorytm, który jako dane przyjmuje tablicę n-elementową, gdzie n jest potęgą dwójki:

Dane:
tablica liczb rzeczywistych T[1..n], gdzie n =2^m, a m jest liczbą całkowitą nieujemną

funkcja uporządkuj(T[1..n]):
jeżeli n = 1
zwróć T[1..n] i zakończ
k ← n/2
A[1..k] ← uporządkuj(T[1 .. k])
B[1..k] ← uporządkuj(T[k+1 .. n])
zwróć scal(A, B) i zakończ

Funkcja scal(A, B) dla danych dwóch tablic o rozmiarze k zwraca tablicę o rozmiarze 2k, powstałą przez połączenie tablic A i B w sposób uporządkowany, tj. od elementu najmniejszego do największego. Na przykład dla tablic A = [4,6,18,22] i B = [1,3,10,15] wywołanie scal(A, B) zwróci tablicę [1,3,4,6,10,15,18,22].