[השמעת מוסיקה] 

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

הרעיון הבסיסי מאחורי המיזוג סוג הוא למיין מערכים קטנים יותר ולאחר מכן לשלב מערכים אלה יחד, או למזג them-- מכאן name-- בסדר ממוין. הדרך שלמזג סוג עושה זאת היא על ידי מינוף כלי נקרא רקורסיה, וזה מה ש אנחנו הולכים לדבר על בקרוב, אבל אנחנו לא באמת דיברנו על עדיין. 

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

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

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

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

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

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

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

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

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

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

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

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

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

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

המחצית השמאלית, הקטן ביותר אלמנט במחצית השמאלית הוא חמש. האלמנט הקטן ביותר ב המחצית הימנית היא אחד. איזה מהם הוא קטן יותר? אחד. 

האלמנט הקטן ביותר ב המחצית השמאלית היא חמש. האלמנט הקטן ביותר ב המחצית הנכונה היא שתי. מה הקטן ביותר? שני. ואז לבסוף חמש ו שום דבר, אנחנו יכולים לומר חמש. 

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

שני הוא פחות משלושה, ולכן שני הולכים. שלוש הוא פחות מ -5, כך שלושה הולכים. ארבעה הוא פחות מ -5, כך ארבעה הולכים. ואז, חמש פחות משישה, ושישה הוא כל מה שנשאר. 

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

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

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

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

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

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

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