מבני נתונים ואלגוריתמים - מחברת קורס/אלגוריתמים/מיון הכנסה ומיזוג/תרגילים/Combine Sort/שאלה

נתון אלגוריתם בשם Combine-Sort המשלב קריאות ל[[מבני נתונים ואלגוריתמים - מחברת קורס/#|]] ו[[מבני נתונים ואלגוריתמים - מחברת קורס/#|]]:

Combine-Sort(Values)
1		return Combine-Sort-Imp(Values, Length(Values))


Combine-Sort-Imp(Values, n)
1	if Length(Values) ≤ √n
2		Insertion-Sort(Values)
3		return Values

4	mid = ⌊1 + Length(Values)⌋ / 2

5	L = Combine-Sort-Imp(Values[1, ... , mid], n)
6	R = Combine-Sort-Imp(Values[mid + 1, ... , Length(Values)], n)

7	return Merge(L, R)

כדאי לדעת: Merge היא פונקציית עזר שכיחה במיונים (לדוגמה [[מבני נתונים ואלגוריתמים - מחברת קורס/#|]]), הלוקחת שני מערכים ממויינים, ומחזירה מערך ממויין שאיבריו איחוד איבריהם. סיבוכיות Merge לינארית בסכום גדלי מערכי הקלט.

מה זמן הריצה של הCombine-Sort? אנא תן חסם טוב ככל האפשר ונמק תשובתך.