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

נתון אלגוריתם מיון \(M\) הפועל באופן הבא:
בהינתן מערך \(A\) באורך \(n\):

• מוצאים את החציון שלו (בעזרת אלגוריתם אופטימלי).
• מבצעים חלוקה סביב החציון (בעזרת אלגוריתם אופטימלי).
• ממיינים את החלק השמאלי (בעזרת אלגוריתם אופטימלי).
• מפעילים את האלגוריתם \(M\) על החלק הימני של החלוקה באופן רקורסיבי.

א. מהם האלגוריתמים האופטימליים בכל שלב?

ב. הוכיחו שהאלגוריתם \(M\) ממיין נכון את המערך.

ג. כתבו נוסחת נסיגה עבור האלגוריתם \(M\) ופתרו אותה.

ד. נבצע את השינוי הבא באלגוריתם: במקום למצוא חציון, נמצא את האיבר במיקום ה-\(n/3\), נבצע את החלוקה סביבו ונמשיך כאמור לעיל. כתבו נוסחת נסיגה עבור האלגוריתם \(M\) ופתרו אותה.