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

הפונקציה Merge עובדת בסיבוכיות $\displaystyle \Theta (|L|+|R|)$, כאשר $\displaystyle |L|$ = Length(L), ו$\displaystyle |R|$ = Length(R).

קל מאד לראות שהלולאה רצה בדיוק $\displaystyle |L|+|R|$ פעמים. בנוסף, כל איטרציה רצה בזמן $\displaystyle O(1)$ - בלי קשר לשאלה איזה רצף של if / else if / else מתבצע, זמן הריצה של איטרציה בודדת עולה לכל הפחות קבוע כלשהו, ולכל היותר קבוע כלשהו. דברים אלה מוכיחים הן את הסופיות והן את ניתוח הסיבוכיות.

כעת נוכיח את הנכונות באינדוקציה.

הוכחה: נוכיח באינדוקציה שבאיטרציה ה$\displaystyle i$ של הלולאה 3-11, מוכנס לMerged האיבר ה$\displaystyle i$ הקטן ביותר.

(בסיס האינדוקציה) באיטרציה הראשונה l וr מצביעים לאיברים הראשונים במערכים. היות שהמערכים ממויינים, בהכרח יבחר האיבר ה1 קטן ביותר (כלומר האיבר הקטן ביותר).

(מעבר האינדוקציה) נניח שהאינדוקציה מתקיימת עד (לא כולל) האיטרציה ה$\displaystyle i$, ונוכיח שהיא מתקיימת גם באיטרציה ה$\displaystyle i$. נשים לב שהיותר שהמערכים ממויינים, אז בשילוב הנחת האינדוקציה והתבוננות בקוד, l וr עברו על כל אחד מ$\displaystyle i-1$ האיברים הקטנים ביותר באיחוד המערכים. היות שהמערכים ממויינים, לפחות אחד מl וr מצביע כעת על אחד האיברים הקטנים ביותר שנותרו. מהתבוננות בקוד, האיבר הזה אכן ייבחר.