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

מתוך ויקיספר, אוסף הספרים והמדריכים החופשי
קפיצה לניווט קפיצה לחיפוש

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


# 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 פועלת בזמן לינארי. נקבל, לכן, את נוסחת הנסיגה , שאותה נוכל לפתור (בין היתר) על ידי הפרישה הבאה:

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

נשים לב שבעץ זה, כל צומת מתאר קריאה אחת של האלגוריתם. צומת הראש, לדוגמה, פועל בזמן , אך מבצע שתי קריאות נוספות.