שורת בלוקים ושאלה אחת
סדרו שורת בלוקים לפי הגובה. עם שמונה בלוקים פשוט מסתכלים, אבל מחשב לא יכול לראות את כל השורה בבת אחת. כל מה שהוא יכול לעשות הוא להרים שני בלוקים, לבדוק איזה מהם גבוה יותר ולהזיז אותם. שיטה לעשות את זה היא אלגוריתם: רשימת צעדים מדויקת מספיק כדי שמכונה תוכל לבצע אותה בלי לחשוב.
כל אלגוריתמי המיון בסצנה בנויים מאותו מהלך. כששני בלוקים עולים מתחת לסוגר, משווים ביניהם. סוגר כחול אומר שהם כבר בסדר הנכון; סוגר כתום אומר שהם מתחלפים. לוחית הפליז סופרת כל השוואה, ומכיוון שהשוואות הן העבודה שכל שיטה חייבת לעשות, הספירה הזאת היא הדרך ההוגנת ביותר לומר כמה עבודה עשתה שיטה.
ארבע דרכים למיין
מיון בועות עובר לאורך השורה, משווה בין שכנים ומחליף כל זוג שאינו בסדר. אחרי מעבר אחד הבלוק הגבוה ביותר “מבעבע” עד הקצה; אחרי המעבר הבא, השני בגובהו; וכן הלאה. אם מעבר מסתיים בלי אף החלפה, השורה ממוינת והמיון נעצר.
מיון הכנסה עובד כמו סידור קלפים ביד. הוא לוקח את הבלוקים אחד אחד ומחליק כל אחד שמאלה, על פני כל בלוק גבוה ממנו, עד שהוא פוגש בלוק נמוך ממנו. החלק השמאלי של השורה ממוין תמיד.
מיון מיזוג מחלק את השורה לשני חצאים, ממיין כל חצי, וממזג את שני החצאים הממוינים: בכל פעם הוא לוקח את הנמוך מבין שני הבלוקים שבראש החצאים. גם החצאים ממוינים באותה דרך, עד לבלוקים בודדים, שממילא ממוינים. בסצנה כל מיזוג בונה את התוצאה שלו על המדף התחתון, ואז מרים אותה בחזרה.
מיון מהיר בוחר בלוק אחד כאיבר ציר, כאן הבלוק האחרון בקטע שהוא ממיין, המסומן בסיכה כתומה קטנה. הוא מעביר כל בלוק נמוך יותר לצד השמאלי של איבר הציר וכל בלוק גבוה יותר לצד הימני שלו, וכך איבר הציר מגיע למקומו הסופי. אחר כך הוא ממיין את שני הצדדים באותה דרך.
נסו: בחרו מיון בועות והעלו את גודל הרשימה עד 64 בלוקים, ואז העבירו את אלגוריתם למיון מיזוג. לאותם 64 בלוקים מיון בועות צריך כ־2,000 השוואות, ומיון מיזוג כ־300.
סופרים את ההשוואות
מיון בועות על שורה הפוכה חייב להשוות כל בלוק לכל בלוק אחר. עם n בלוקים יש n(n − 1)/2 זוגות: 28 עבור 8 בלוקים, 2,016 עבור 64. הכפילו את השורה, והעבודה גדלה בערך פי ארבעה. מיון הכנסה עושה בערך מחצית מזה על שורה מעורבבת, אבל הוא גדל באותו אופן. מדעני מחשב כותבים את הגדילה הזאת כ־O(n²), וקוראים זאת “מסדר גודל n בריבוע”.
מיון מיזוג עושה פחות עבודה, כי כל השוואה במיזוג קובעת סופית את מקומו של בלוק אחד ברצף הממוזג. אפשר לחצות את השורה רק כ־log₂n פעמים (6 פעמים עבור 64 בלוקים), ובכל סבב של מיזוג כל בלוק מושווה לכל היותר פעם אחת, כך שהסך הכול הוא לכל היותר בערך n × log₂n: לכל היותר 321 השוואות עבור 64 בלוקים. מיון מהיר על שורה מעורבבת צריך בממוצע קצת יותר, כ־360 השוואות עבור 64 בלוקים. זו גדילה של O(n log n), ושום שיטה שעובדת רק בהשוואת זוגות לא יכולה לעשות טוב ממנה, אפילו בממוצע.
בחרו גדילה בהצגת קצב הגדילה כדי לראות את שתי העקומות זו לצד זו. הרצועה הכתומה היא n(n − 1)/2, והכחולה היא n log₂n. העקומה הלבנה היא הספירה של האלגוריתם שנבחר בכל גודל רשימה, בממוצע על פני 24 שורות התחלה מהסוג שנבחר, והנקודה מטפסת ככל שהריצה הנוכחית סופרת.
שורת ההתחלה משנה
אותו אלגוריתם יכול להיות מהיר או איטי, תלוי בשורה שהוא מקבל. על שורה בסדר כמעט ממוין מיון הכנסה כמעט לא מזיז דבר: כל בלוק מושווה פעם או פעמיים ונשאר במקומו, ולכן הספירה קרובה ל־n. זו הסיבה שמיון הכנסה עדיין משמש לרשימות קטנות או כמעט מסודרות.
המיון המהיר שכאן הוא ההפך. בחירת הבלוק האחרון כאיבר ציר עובדת טוב על שורה מעורבבת, אבל על שורה ממוינת או בסדר הפוך איבר הציר הוא תמיד הבלוק הגבוה ביותר או הנמוך ביותר שנשאר. כל חלוקה משאירה אז צד אחד ריק, והספירה מטפסת ל־n(n − 1)/2, גרוע כמו מיון בועות. ספריות אמיתיות בוחרות את איבר הציר מהאמצע, מתוך מדגם או באקראי, ויש שעוברות לשיטה אחרת כשהחלוקות משתבשות.
מה המודל הזה משאיר בחוץ
הספירות מדויקות לארבע התוכניות האלה, וכל אחת מהן אפשר היה לכתוב קצת אחרת: מיון בועות בלי העצירה המוקדמת, או מיון מיזוג שמדלג על מיזוג של חצאים שכבר מסודרים, היו סופרים אחרת. ההשוואות אינן כל המחיר. מיון מיזוג צריך מדף שני באורך השורה, ואילו האחרים ממיינים במקום; גם החלפה או העתקה לוקחות זמן, ובמחשב אמיתי הסדר שבו ניגשים לזיכרון יכול להשפיע לא פחות מהספירה. נתונים אמיתיים מביאים גם ערכים חוזרים ורשומות שחייבות לשמור על הסדר המקורי שלהן, ואת זה הבלוקים כאן, שכולם בגבהים שונים, חוסכים. לבסוף, הסצנה מנגנת כל גודל רשימה בקצב משלו, מהר יותר לרשימות ארוכות, ולכן השוו זמנים על המסך רק באותו גודל רשימה.