מיון מהיר (quicksort או QS בקיצור) פועל ע"י (1) בחירת איבר חלוקה K (שמטעמי עצלות נבחר לעיתים קרובות כ־K=A[1]), (2) חלוקת n האיברים במערך A ל־2 קבוצות S1 ו־S2 שמכילות, בהתאמה, את האיברים הקטנים מ־K ואת האיברים הגדולים מ־K וסידור המערך מחדש ל־S1,K,S2, ז"א K במקומו המיועד, משמאלו איברי S1 ומימינו איברי S2, ו־(3) המשך רקורסיבי על S1 ועל S2.
הוכח/י שמיון מהיר אופטימלי בממוצע, כאשר בכל השאלה הממוצע מתייחס לכך שהמיקום בסידור הממויין של איבר החלוקה יכול להיות בכל אחד מ־n המקומות, בהסתברות שווה.
הדרכה: נגדיר T(n) - מספר השוואות ממוצע כדי למיין n איברים ע"י QS.
א) T(n)=a(n)+b(n)∑i=1nc(i) כאשר a(n)=n+1 הוא מספר ההשוואות לביצוע החלוקה, b(n)=n1 היא ההסתברות שאיבר החלוקה יפול למקום ה־i, ו־c(i) היא עלות ההמשך הרקורסיבי במקרה שאיבר החלוקה יפול למקום ה־i, ועליכם למצוא את c(i) במונחים של T. רשמו את הנוסחה הרקורסיבית שמתקבלת עבור T(n).
ב) הכפל/י את 2 צידי המשוואה ב־n כדי לטפל רק במספרים שלמים.
ג) נסחו משוואה דומה אך שונה: עם פרמטר n−1 במקום n.
ד) צרו משוואה חדשה ע"י חיסור אגף אגף של המשוואות הקודמות, וסידור מחדש.
ה) חלקו את שני האגפים ב־(n+1)n.
ו) הגדירו H(n)=n+1T(n), וקבלו נוסחה רקורסיבית עבור H(n).
ז) פתרו עבור H(n) והסיקו ל־T(n). מה המסקנה בענין האופטימליות של QS?