Mamy więc drzewo o głębokości na każdym poziomie dokonujemy scalenia o łącznym koszcie gdzie jest stałą zależną od komputera. A więc intuicyjnie, tzn. nieformalnie możemy dowieść, że złożoność algorytmu mergesort to
Formalnie złożoność czasową sortowania przez scalanie możemy przedstawić następująco:
Bez straty ogólności załóżmy, że długość ciągu, który mamy posortować jest potęgą liczby 2:
Ciągi jednoelementowe możemy posortować w czasie stałym, czas sortowania ciągu -elementowego to scalenie dwóch ciągów -elementowych, czyli O(n), plus czas potrzebny na posortowanie dwóch o połowę krótszych ciągów.
Mamy:
gdzie
Po rozwinięciu nawiasów otrzymamy:
A więc asymptotyczny czas sortowania przez scalanie wynosi O(n log n) (zobacz: notacja dużego O).
Przypisy
Linki zewnętrzne Przyśpieszony MergeSort Algorytm przedstawiony z wykorzystaniem tańca
Scalanie