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

להלן הפסוודו-קוד של מיון מיזוג:

# Merge sort. 
# Takes an array (Values).
# Returns an array of the same elements, sorted in increasing order.
Merge-Sort(Values)
1	if Length(Values) <= 1
2		return Values

3	mid = ⌊(1 + Length(Values)) / 2⌋
		
4	L = Merge-Sort( Values[1, ... , mid] )
5	R = Merge-Sort( Values[mid + 1, ... , Length(Values)] )
	
6	return Merge(L, R)

הפונקציה Merge פועלת בזמן לינארי. נקבל, לכן, את נוסחת הנסיגה $\displaystyle T(n)=2\cdot T(n/2)+\Theta (n)$, שאותה נוכל לפתור (בין היתר) על ידי הפרישה הבאה:

עץ הפרישה של מיון מיזוג.

נשים לב שבעץ זה, כל צומת מתאר קריאה אחת של האלגוריתם. צומת הראש, לדוגמה, פועל בזמן $\displaystyle \Theta (n)$, אך מבצע שתי קריאות נוספות.