Merge Sort und Auswahl Sortieren

Question

Ich habe Probleme beim Entwickeln der Wiederholung für einen Algorithmus, der rekursive Merge Sort-Aufrufe für Listengrößen größer als m verwendet. Es verwendet Auswahl Sortieren für Listengrößen kleiner oder gleich m.

Hier ist mein Pseudo-Code:

proc merge_and_selection (A, p, r, m) { 
if (p <= r) then 
    q = (p + r)/2 

    if r - p > m then 
     merge_and_selection(A, p, q - 1, m) 
     merge_and_selection(A, q + 1, r, m) 
    else 
     selection_sort(A, p, q - 1) 
     selection_sort(A, q + 1, r) 
    end 

    merge(A, p, q, r) 
end if 
} 

ich denke, die Wiederholung ist:

mit T (2) = [m (m-1)]/2

Answer 1

Ich denke, genauere Formel ist die folgende:

• T (n) = 2 * T (n/2) + Theta (n) für n> = m/2
• T (n) = Theta (n^2) für n < m/2