מיון מהיר של מיונים איטיים

היום נדבר על אלגוריתמים למיון, אבל לפני שנתחיל להציג אלגוריתמים קונקרטיים, בואו נענה על השאלה האקוטית שחלקכם בוודאי תוהים לגביה - מה זה בכלל אלגוריתם?

המילה אלגוריתם מגיעה משיבוש שמו של המתמטיקאי הפרסי מוחמד אבן מוסא אל-ח’ואריזמי, אחד מגדולי המתמטיקאים של ימי הביניים (בימי הביניים, בזמן שאירופה הייתה בחור שחור מאין כמותו, המתמטיקה פרחה במקומות אחרים ובעולם המוסלמי בעיקר). אל-ח’ואריזמי כתב את אחד מהספרים החשובים במתמטיקה - “חיסאב אל-ג’אבר ואל-מוקאבלה”, שעסק בפתרון משוואות ממעלה שניה (המילה “אלגברה” מגיעה מה”אל-ג’אבר” שבשם הספר). ספר אחר שלו עסק בחישובים בעזרת ספרות הודיות - ליתר דיוק, בעזרת שיטת כתיבת המספרים ההודית, השונה מאוד מזו הרומאית. בשיטה זו אנו משתמשים עד היום. אחד מהיתרונות בשיטה הזו היא הקלות הרבה שבה ניתן לבצע פעולות חשבון; זה כל כך קל עד שילדים לומדים את זה כבר בבית הספר היסודי. למשל, איך מחברים שני מספרים? כותבים האחד מעל השני, ספרה-ספרה, כאשר הספרות הימניות ביותר של המספרים נמצאות זו מעל זו, ואז עוברים ספרה-ספרה מימין לשמאל, מחברים את הספרות, כותבים את הספרה הראשונה של התוצאה וזוכרים את היתר (מה שמקבלים אחרי ש”חותכים” את הספרה הימנית ביותר ממנו), ומחברים אותו לשתי הספרות הבאות, וכן הלאה. זו דוגמה לאלגוריתם.

אלגוריתם באופן כללי הוא תיאור פשוט של תהליך שמטרתו לפתור בעיה. הפשטות היא קריטית - האלגוריתם תמיד צריך לכלול סדרה של צעדים פשוטים שכל אחד מהם הוא קל מספיק כדי שלקורא יהיה ברור איך אפשר לבצע אותו. כמו כן צריך שהאלגוריתם תמיד יסיים את עבודתו תוך פרק זמן סופי ושתוצאות האלגוריתם תהיה נכונה. כל תוכנית מחשב היא דוגמה לאלגוריתם, אם כי לרוב מעדיפים לכתוב אלגוריתמים בשפה שהיא חופשית קצת יותר מאשר תוכנית מחשב. אני אנקוט בדרך ביניים שמשלבת את הרע מבין שני העולמות - אתאר אלגוריתמים באופן לא פורמלי, שבו אני לא מסביר כל צעד עד הסוף; ואציג קוד מחשב “אמיתי” שפותר את הבעיה, בשפה שאף אחד לא מכיר (Ruby).

עכשיו משסיימנו עם המבוא, בואו נעבור לאקשן.

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

“מיון”, בעברית, משמש באופן אומלל למדי לתיאור שני דברים שונים. האחד הוא Classification - בהינתן קבוצת אובייקטים, לחלק אותם לתת-קבוצות על פי תכונה שלהם (“יונקים”, “זוחלים”, “חרקים”). זו לא הבעיה שאני מדבר עליה, אלא Sorting - בהינתן רשימה של אובייקטים שמוגדר עליהם סדר כלשהו, לסדר אותה.

לרשימה אני אקרא \( A \), ואת האיבר במקום ה-\( i \) ברשימה אסמן בתור \( A\left[i\right] \). ההנחה היא שיש סדר על הרשימה, כלומר שלכל \( i\ne j \) מתקיים \( A\left[i\right]<A\left[j\right] \) או \( A\left[j\right] < A\left[i\right] \). המטרה היא לסדר מחדש את הרשימה כך שיתקיים \( A\left[0\right] < A\left[1\right] < A\left[2\right]<\dots<A\left[n\right] \) (שימו לב שאני מתחיל את האינדקס מאפס, כפי שנהוג במדעי המחשב; יש לשיטה הזו יתרונות וחסרונות ואני בוחר בה כדי להתאים לקוד שאני אכתוב כאן).

מהם אברי הרשימה \( A \)? אניח שהם מספרים שלמים, רק לצורך פשטות. באופן כללי הם יכולים להיות אובייקטים מורכבים מאוד, וההשוואה בין שניהם יכולה להיעשות בצורה מחוכמת מאוד. רוב האלגוריתמים שאציג פה לא יתעניינו בכך - כל מה שהם יצטרכו לדעת לצורך תהליך המיון זה המידע הבא: בהינתן שני איברים \( a,b \) האם \( a<b \) או \( b < a \) (או שהם שווים). יש גם אלגוריתמים שיכולים להיעזר בכך שהם יודעים משהו על סוג האיברים שממיינים, אבל דיה לצרה בשעתה.

אז הנה דוגמה פשוטה. נניח ש-\( A=\left[1,4,2,3\right] \). אחרי מיון נרצה לקבל \( A=\left[1,2,3,4\right] \). איך אפשר לעשות זאת? השיטה הראשונה שאני מעלה על דעתי היא זו: נעבור על \( A \) ונמצא את האינדקס שבו נמצא האיבר הגדול ביותר. מצאנו? נחליף את האיבר הזה עם האיבר שנמצא כרגע בסוף הרשימה. עכשיו אנחנו יודעים שהאיבר בסוף הרשימה נמצא במקומו הנכון ולכן אפשר לחשוב על הסיטואציה כאילו הרשימה קטנה ב-1. נעבור מחדש על הרשימה הקטנה יותר ונמצא את האיבר המקסימלי בה, נחליף אותו עם האיבר שנמצא כרגע בסוף הרשימה (הרשימה הקטנה ב-1), וכן הלאה וכן הלאה. הנה קוד שעושה את זה:

def selection_sort(list)
  list.length.downto(1) do |k|
    max_index = 0
    for i in 1...k do
      max_index = i if list[max_index] < list[i]
    end
    list.swap(max_index,k-1)
  end
  return list
end

קצת על רובי, כדי שהקוד יהיה קריא בכל זאת גם למי שלא מכיר שפות תכנות בכלל:

ברובי, def מתאר הכרזה על שם של פונקציה, כלומר קטע קוד שמקבל קלט (במקרה שלנו הקלט הוא ה-list שמופיע בסוגיים, שהוא על תפקיד ה-\( A \) שלנו), ובסופו של דבר מחזיר פלט (אבל יותר מעניין אותנו כאן דווקא המניפולציות שעושים על הקלט - ממיינים את list ישירות, אם כי בסוף גם מחזירים אותה). הפונקציה מסתיימת ב-end שלמטה.

בתוך הפונקציה יש לולאות. לולאה היא קטע קוד שחוזר על עצמו שוב ושוב; לפעמים יש משתנה מיוחד כלשהו (המונה) שהערך שלו משתנה בין כל הרצה של הלולאה (הרצה כזו נקראת איטרציה). כך גם אצלנו:

list.length.dowto(1) do |k|

זו דרך לרשום “עכשיו תעשה לולאה שהמונה שלה, שנקרא לו k מתחיל מהערך list.length (אורך הרשימה) ובכל איטרציה המונה קטן ב-1 עד שהוא מגיע ל-1 (וכשהוא מגיע ל-1 תריץ את הלולאה פעם אחת אחרונה וצא ממנה)”.

אחרי השורה הזו מגיע הגוף של הלולאה - מה שמתבצע בכל איטרציה - ומסתיים ב-end שלפני ה-return list (זו, באופן מפתיע, השורה שבה מחזירים את המערך הממויין).

המשמעות של k היא “האורך של הרשימה שכרגע אנחנו ממיינים” - זכרו שבכל איטרציה, האורך הזה באמת אמור לקטון ב-1.

קטע הקוד הבא מוקדש למציאת האיבר המקסימלי ברשימה הנוכחית. אז קודם כל יוצאים מתוך ברירת מחדל שהאיבר המקסימלי נמצא במקום 0, וזה פשוט max_index = 0, וכעת מבצעים לולאה נוספתת שמחפשת ברשימה את האינדקס של האיבר המקסימלי.

הלולאה נפתחת ב-for i in 1…k do, שגם אותו צריך להסביר. כאן משתנה הלולאה הוא ה-i שבא מייד אחרי ה-for; ואילו 1…k מייצג את “כל המספרים השלמים מ-1 ועד k, לא כולל k’’. אצלנו i יתחיל מ-1 ויגדל ב-1 כל פעם עד שיגיע ל-k, ואז נצא מהלולאה (בלי להריץ אותה עבור i=k). הסיבה שאנחנו לא מגיעים עד k היא פשוטה: ברובי, כמו ברוב שפות התכנות, האיבר הראשון ברשימה הוא איבר מספר 0, ולכן אם אורך הרשימה הוא \( n \) אז האיבר האחרון בה הוא איבר מספר \( n-1 \). זה משהו מבלבל ואיום ונורא למי שכרגע נתקל בו לראשונה, אבל מתרגלים אליו ורואים שהוא חשוב מאוד לפעמים. במילים אחרות - הרבה אלגוריתמים הם פשוטים יותר בגלל זה, אבל גם הרבה אלגוריתמים הם מסובכים יותר בגלל זה. אני אישית דבק בקונבנציה הזו כי זה מה שקורה בשפות תכנות. בפועל. בעולם האמיתי. כשתרצו ללכת ולכתוב קוד, זה מה שתצטרכו לעשות. מקומות אחרים (למשל הספר של CLRS שהוא התנ”ך של מבוא לאלגוריתמים) מתחילים דווקא מ-1. אין תשובה טובה לשאלה “מה נכון” פרט ל”זה הבלוג שלי. אל תריבו!”

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

בסיום הלולאה הפנימית (ה-end שאחרי השורה של הבדיקה-והשמה) אנחנו מחליפים בין האיבר האחרון במערך כרגע (זה האיבר במקום \( k-1 \)) ובין האיבר במקום המקסימלי, וזאת על ידי הפקודה (list.swap(max_index, k-1. לא הסברתי איך אני מבצע החלפה בין שני איברים במערך. ברובי אפשר לעשות את זה בשורה אחת:

list[i], list[j] = list[j], list[i]

קטע הקוד הזה מחליף את האיברים במקומות \( i,j \) ברשימה. אני משתמש ב-list.swap במקום זה רק כדי לשפר את הקריאות. בפועל, בשפה ברמה יותר בסיסית מאשר רובי, צריך להשתמש במשתנה עזר כלשהו כדי לזכור את הערך שהיה באחד המקומות ברשימה לצורך ההחלפה (תרגיל נחמד: כאשר הרשימה כוללת מספרים, אפשר להחליף שני תאים בלי שום משתני עזר - איך?)

האם האלגוריתם שלמעלה (שאני קורא לו “מיון-בחירה”, כי בוחרים בכל פעם את האיבר שצריך להיכנס לסוף הרשימה) הוא טוב או רע? ובכן, הוא פשוט מאוד להבנה, וזה טוב. אבל הוא עושה הרבה עבודה: מספר האיטרציות שלו הוא כגודל המערך, ובכל איטרציה יש לולאה פנימית, שעושה הרבה השוואות. באיטרציה הראשונה יש \( n-1 \) השוואות (כש-\( n \) הוא אורך הרשימה); בשניה יש \( n-2 \) השוואות; בשלישית יש \( n-3 \) וכן הלאה. סך הכל \( \left(n-1\right)+\left(n-2\right)+\cdots+1=\frac{\left(n-1\right)\left(n-2\right)}{2}=\Theta\left(n^{2}\right) \) השוואות. בנוסף יש גם \( \Theta\left(n\right) \) החלפות, אבל זה פחות נורא. בסך הכל האלגוריתם הוא לא אסון אבל יש טובים ממנו שעוד נראה.

המשמעות של סיבוכיות ריבועית שכזו היא שעבור רשימה של 1,000 פריטים צריך סדר גודל של מיליון השוואות; עבור רשימה של מיליון פרטים (וזו סיטואציה אפשרית בהחלט) צריך סדר גודל של \( 10^{12} \) השוואות - זה לא משהו בכלל. כבר על רשימות קטנות יחסית האלגוריתם דורש זמן ריצה מורגש, גם במחשבים מודרניים (אערוך השוואות כלשהן בהמשך, אחרי שאציג את כל אלגוריתמי המיון).

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

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

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

def insertion_sort(list)
  for k in 1...list.length
    new_element = list[k]
    i = k-1
    while i >= 0 and list[i] > new_element
      list[i+1] = list[i]
      i = i - 1
    end
    list[i+1] = new_element
  end
  return list
end

בתחילת ריצת האלגוריתם מתייחסים לתא 0 לבדו בתור “רשימה ממוינת” (לא חוכמה, זו רשימה של איבר אחד) ואילו כל היתר הוא מערב פרוע. לאט לאט מגדילים את האיזור הממויין על ידי כך שלוקחים את האיבר הראשון שהוא מחוץ לאיזור הממויין (האיבר במקום ה-k) ועוברים על האיזור הממויין מהסוף להתחלה תוך שאנו דוחפים קדימה את האיברים שאנו חולפים על פניהם, עד שאנו מוצאים את המקום הנכון להכניס אליו את האיבר החדש (בדיוק המקום שבו כל האיברים שחלפנו על פניהם היו גדולים מ-k והאיבר הראשון שטרם חלפנו על פניו קטן מ-k).

ניתוח הסיבוכיות כאן יותר מסובך. ללולאה החיצונית יש n-1 איטרציות, אבל הלולאה הפנימית היא לולאה מסוג חדש - לולאת while, שממשיכה לרוץ כל עוד תנאי מסויים לא התקיים. התנאי הוא שטרם מצאנו את המקום שאליו צריך להכניס את האיבר החדש. לכל היותר זה ייקח לנו k צעדים, אבל ייתכן שזה יקח לנו גם הרבה פחות. אז מה עושים?

לרוב הניתוח מתבסס על המקרה הגרוע ביותר. מה יהיה המקרה הגרוע ביותר כאן? אם תמיד האיבר החדש יהיה קטן מכל האיברים שכרגע נמצאים ברשימה הממויינת. זה יכול לקרות אם list כבר ממוין, אבל בדיוק בסדר הפוך (מהגדול ביותר לקטן ביותר). במקרה הזה בכל איטרציה יהיו לנו \( O\left(k\right) \) השוואות ו-\( O\left(k\right) \) החלפות, ולכן בסך הכל נקבל שהאלגוריתם מבצע \( \Theta\left(n^{2}\right) \) החלפות ו-\( \Theta\left(n^{2}\right) \) השוואות. זה עוד פחות טוב ממיון-בחירה. מצד שני, שימו לב שהאלגוריתם לא בדיוק מבצע “החלפה” - הוא מבצע חצי החלפה בלבד בכל פעם (לא השתמשתי ב-swap), אז הנזק פחות גדול משנראה במבט ראשון.

מצד שני, הביצועים במקרה הגרוע ביותר הם ממש לא המדד היחיד שצריך לחשוב עליו. למיון-בחירה יש חסרון לפיו הוא תמיד ידרוש ביצוע של \( \Theta\left(n^{2}\right) \) השוואות; לעומת זאת מיון הכנסה עשוי לדרוש הרבה, הרבה פחות פעולות אם הקלט יהיה “נחמד” (למשל, אם הרשימה ממויינת ברובה כבר כך - סיטואציה מציאותית יחסית).

בואו נעבור למיון פשוט נוסף - מיון בועות. השם של המיון הזה מגיע מכך שבשיטה שלו, בכל איטרציה האיבר הגדול ביותר שטרם טופל “מפעפע למעלה” למקומו במערך. השיטה פשוטה: מתחילים מהשוואה בין \( A\left[0\right] \) ו-\( A\left[1\right] \). אם \( A\left[0\right]<A\left[1\right] \) הכל בסדר, אבל אם \( A\left[1\right]<A\left[0\right] \) אז מחליפים ביניהם. כעת אנו יודעים שב-\( A\left[1\right] \) יש את האיבר הגדול מבין שני הראשונים; משווים אותו עם \( A\left[2\right] \). אם \( A\left[2\right]<A\left[1\right] \), מחליפים, וכעת ב-\( A\left[2\right] \) יש את האיבר הגדול מבין שלושת הראשונים. ממשיכים… ובסוף התהליך ב-\( A\left[n\right] \) יהיה את האיבר הגדול ביותר ברשימה. עכשיו אפשר להתחיל את כל הסיפור מחדש אבל לעצור ב-\( A\left[n-1\right] \), וכן הלאה.

def bubble_sort(list)
  list.length.downto(1) do |n|
    for i in 0...(n-1) do
      list.swap(i,i+1) if list[i] > list[i+1]
    end
  end
  return list
end

האלגוריתם הזה הוא איום ונורא. הוא גם לא טריוויאלי לחלוטין להבנה מבחינה רעיונית (למרות שאחרי שמבינים, הקוד עצמו הוא פשוט מאוד), והוא גם משיג בפועל תוצאות שהן משמעותית גרועות יותר מאשר אלו של מיון הכנסה ומיון-בחירה. הסיבה לכך היא שהוא מבצע גם המון השוואות (\( \Theta\left(n^{2}\right) \) תמיד - למה?) וגם המון החלפות, במקרים גרועים. במקרה טוב, למשל אם המערך כבר ממוין, הוא ישיג ביצועים טובים יותר מאשר מיון-בחירה, אבל בדרך כלל הביצועים שלו יהיו גרועים משמעותית יותר מאלו של מיון-בחירה ומיון הכנסה. אל תשתמשו בו. פשוט אל.

עד כה כל האלגוריתמים פעלו בזמן שהוא \( \Theta\left(n^{2}\right) \) במקרה הגרוע. הגיע הזמן לראות אלגוריתם מיון טוב, כזה שפועל בזמן \( \Theta\left(n\log n\right) \) ולכן משיג ביצועים טובים יותר משמעותית מכל האלגוריתמים שהצגתי. נתחיל ממיון שהוא פשוט יחסית להצגה, אבל הוא חזק מאוד (יש ספריות שמשתמשות בו בתור אלגוריתם המיון שלהן) - מיון מיזוג, שהומצא על ידי המתמטיקאי ג’ון פון-נוימן בשנת 1945 (ראשית ימי מדעי המחשב).

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

האבחנה הזו די ברורה אם מסתכלים על האלגוריתמים שכבר התעסקנו בהם. מיון נאיבי של רשימה לוקח \( n^{2} \) צעדים, נאמר? אז מיון נאיבי של רשימה שגודלה \( \frac{n}{2} \) יקח \( \left(\frac{n}{2}\right)^{2}=\frac{n^{2}}{4} \) צעדים, ולכן מיון של שתי רשימות שגודלן \( \frac{n}{2} \) יקח רק \( \frac{n^{2}}{2} \) צעדים - חצי מספר הצעדים מאשר מיון של הרשימה הגדולה. כמובן, זה בפני עצמו עדיין לא מהווה שיפור גדול במיוחד, אבל אחרי שמפצלים את הרשימה הגדולה לשתי רשימות קטנות, אפשר כדי למיין אותן לפצל אותן שוב לשתי רשימות כל אחת, ושוב ושוב ושוב. זו דוגמה לאלגוריתם רקורסיבי; אלגוריתם שמפעיל את עצמו על מקרים קטנים ופשוטים יותר של הבעיה. המקרה הכי פשוט הוא רשימה מגודל 0 או 1; רשימה כזו היא ממויינת בהכרח מעצמה, בלי שנעשה שום דבר נוסף איתה.

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

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

הנה הקוד של המיון:

def merge_sort(list)
  return list if list.length <= 1
  k = list.length / 2
  list_a = merge_sort(list[0...k])
  list_b = merge_sort(list[k...list.length])
  return merge(list_a, list_b)
end

כמו שאנחנו רואים, הוא פשוט מאוד - אפילו טריוויאלי. פשוט מחלקים את הרשימות לשני חלקים באמצע (אלא אם הרשימה שלנו מכילה לכל היותר איבר אחד ואז לא עושים כלום), ממיינים כל אחת משתי הרשימות בנפרד ובסוף ממזגים. כדי להשלים את התמונה צריך להציג את האלגוריתם שממזג. כאן, למרבה הצער, הקוד יוצא טיפה מסורבל, אם כי לא נורא:

def merge(list_a, list_b)
  i, j = 0, 0
  result = []
  while i < list_a.length and j < list_b.length
    if (list_a[i] < list_b[j])
      result.push(list_a[i])
      i = i + 1
    else
      result.push(list_b[j])
      j = j + 1
    end
  end

  while i < list_a.length
        result.push(list_a[i])
        i = i + 1
  end

  while j < list_b.length
        result.push(list_b[j])
        j = j + 1
  end
  return result
end

נשאר רק להבין מה סיבוכיות זמן הריצה של האלגוריתם הזה. ראשית כל, שימו לב שאם merge מופעל על שתי רשימות שהארוכה מביניהן היא באורך \( n \), אז זמן הריצה שלו הוא \( \Theta\left(n\right) \) (עוברים על לכל היותר \( 2n \) איברים). במילים - מיזוג ניתן לבצע בזמן לינארי.

כדי להבין כמה זמן נדרש מ-merge_sort לרוץ צריך להתאמץ טיפה יותר. הקושי כאן הוא שמדובר על אלגוריתם רקורסיבי - כזה שקורא לעצמו - ולכן צריך להתחכם קצת בניתוח. בואו נסמן את זמן הריצה של האלגוריתם ב-\( T\left(n\right) \). אז ברור ש-\( T\left(1\right)=O\left(1\right) \) (כי על רשימה מגודל 1 האלגוריתם רק מבזבז זמן על בדיקה האם הרשימה מגודל 1 או פחות וזהו).

אם לעומת זאת \( n \) גדול יותר, אנחנו מקבלים את המשוואה הבאה שמתארת את זמן הריצה של האלגוריתם:

\( T\left(n\right)=2T\left(\frac{n}{2}\right)+\Theta\left(n\right) \)

מה המשוואה בעצם אומרת? שהזמן שלוקח להריץ את המיון על רשימה בגודל \( n \) שווה לזמן שלוקח להריץ את המיון על שתי רשימות בגודל \( \frac{n}{2} \) (\( 2T\left(\frac{n}{2}\right) \) - זה שלב ה”הפרד”) ועוד הזמן שלוקח למזג אותן אחר כך (\( \Theta\left(n\right) \) - זה ה”ומשול”). יופי, איך מתקדמים מכאן? - פשוט משתמשים באותה נוסחה שוב, ומקבלים:

\( 2T\left(\frac{n}{2}\right)+\Theta\left(n\right)=2\left(2T\left(\frac{n}{4}\right)+\Theta\left(\frac{n}{2}\right)\right)+\Theta\left(n\right)=4T\left(\frac{n}{4}\right)+\Theta\left(n\right) \)

מפתה לעבור עכשיו לטענה כללית: שלכל \( k \) טבעי, מתקיים:

\( T\left(n\right)=2^{k}T\left(\frac{n}{2^{k}}\right)+\Theta\left(n\right) \)

ואז לומר “בואו נבחר \( k \) כך ש-\( 2^{k}=n \) ואז נקבל \( T\left(n\right)=n+\Theta\left(n\right)=\Theta\left(n\right) \) וקיבלנו זמן ריצה לינארי של האלגוריתם”. רק שזה לא נכון. זו נקודה עדינה ומבלבלת שחשוב להתייחס אליה, אז בואו נעשה את זה.

מה \( T\left(n\right)=\Theta\left(n\right) \) אומר? שקיים קבוע \( c \) וקיים \( N \) כך ש-\( T\left(n\right)<c\cdot n \) לכל \( n>N \) (יש גם חסם מלמטה אבל הוא לא חשוב כרגע).

מה \( T\left(n\right)=2^{k}T\left(\frac{n}{2^{k}}\right)+\Theta\left(n\right) \) אומר? שלכל \( k \), קיים קבוע \( c_{k} \) וקבוע \( N_{k} \) כך ש-\( T\left(n\right)<2^{k}T\left(\frac{n}{2^{k}}\right)+c_{k}n \) לכל \( n>N_{k} \).

האם אפשר לעבור מהטענה השניה לראשונה על ידי הצבת \( k=n \)? לא! כי \( n \) אינו קבוע. זכרו - אנחנו מנסים לחסום פה פונקציה של \( n \). בקיצור, האינטואיציה פכמהה מסוכנת ובעייתית. משחקי \( \Theta \) עלולים להוביל לבעיות מסוג זה.

הדרך להתגבר על הבעיה היא ניתוח קצת יותר זהיר. אנחנו יודעים ש-\( T\left(n\right)=2T\left(\frac{n}{2}\right)+\Theta\left(n\right) \). זה אומר ש\( T\left(n\right)<2T\left(\frac{n}{2}\right)+c\cdot n \) לכל \( n>N \) עבור \( N,c \) מסויימים. יפה. עכשיו ניטרלנו (לעת עתה) את הסימונים האסימפטוטיים מהמשוואה. כדי לסיים עם זה, נשים לב לכך שעבור \( n<N \) מתקיים \( T\left(n\right)<d \) עבור קבוע \( d \) כלשהו. אם נבחר את \( c \) להיות גדול מספיק, ובפרט גדול יותר מ-\( d \), נקבל ש-\( T\left(n\right) < 2T\left(\frac{n}{2}\right)+c\cdot n \) היא משוואה שתקפה תמיד, לכל \( n \).

עכשיו אפשר לעשות את התעלול הבא:

\( T\left(n\right)<2T\left(\frac{n}{2}\right)+c\cdot n<2\left(2T\left(\frac{n}{4}\right)+c\cdot\frac{n}{2}\right)+c\cdot n=4T\left(\frac{n}{4}\right)+2cn \)

שימו לב: ה-\( 2cn \) שבאגף ימין נבנה מה-\( cn \) שהיה בהתחלה, ועוד פעמיים \( c\frac{n}{2} \) (המחיר של הפעלת מיזוג על שני תתי-הרשימות).

נחזור על הקסם שוב:

\( 4T\left(\frac{n}{4}\right)+2cn<4\left(2T\left(\frac{n}{8}\right)+c\frac{n}{4}\right)+2cn=8T\left(\frac{n}{8}\right)+3cn \)

הבנתם את הרעיון. הנה המשוואה הכללית, שנכונה לכל \( k \) טבעי:

\( T\left(n\right)<2^{k}T\left(\frac{n}{2^{k}}\right)+k\cdot cn \)

ולכן עבור \( k \) שמקיים \( 2^{k}\ge n \) יתקיים ש- \( T\left(\frac{n}{2^{k}}\right)<d \) עבור איזה שהוא קבוע \( d \). נשאלת רק השאלה איזה \( k \) לבחור.

אם \( 2^{k}=n \), יש סימון מיוחד ל-\( k \) שמקיים את השוויון: \( k=\lg n \) (זה מה שנקרא לוגריתם על בסיס 2). לא תמיד \( n \) הוא בדיוק חזקה של 2, ולכן לא תמיד \( \lg n \) יוצא מספר שלם. תמיד אפשר לעגל למעלה: \( k=\left\lceil \lg n\right\rceil \), והמספר שנקבל יקיים \( n\le2^{k}\le2n \). לכן אנחנו מקבלים בסופו של דבר את אי השוויון הבא:

\( T\left(n\right)<2n\cdot d+\left\lceil \lg n\right\rceil \cdot cn=O\left(n\log n\right) \)

(הסיבה שעברתי מ-\( \lg \) ל-\( \log \) היא שכדי לעבור בין שני בסיסים שונים של לוגריתם כופלים בקבוע: \( \log_{a}n=\left(\log_{a}b\right)^{-1}\cdot\log_{b}n \), ולכן \( \log_{a}n=\Theta\left(\log_{b}n\right) \)).

קיבלנו חסם עליון על הזמן שבו רץ האלגוריתם, ולא קשה במיוחד להראות חסם תחתון דומה. המסקנה: מיון מיזוג רץ בזמן \( \Theta\left(n\log n\right) \), שהוא טוב משמעותית יותר מאשר \( \Theta\left(n^{2}\right) \), שכן \( \log n \) הוא קטן משמעותית ביחס ל-\( n \). ההבדל שבין \( n \) ו-\( \log n \) הוא ההבדל שבין גודל של מספר ובין מספר הספרות של אותו מספר (בבסיס עשרוני, או בינארי, לא באמת חשוב). כך למשל הגודל של 10 הוא עשר, ואילו מספר הספרות שלו הוא 2; ואילו מספר הספרות של \( 10^{100} \) הוא בסך הכל 101, בעוד הגודל של המספר הזה (גוגול) הוא גדול ממספר האטומים ביקום. התוצאה היא הבדל משמעותי ביותר בביצועים.

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