[מוזיק פּלייינג] 

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

די גרונט געדאַנק הינטער צונויפגיסן סאָרט איז צו סאָרט קלענערער ערייז און דעמאָלט פאַרבינדן די ערייז צוזאַמען, אָדער צונויפגיסן טהעמ-- דעריבער די נאַמע-- אין אויסגעשטעלט סדר. די וועג וואָס צונויפגיסן סאָרט טוט דעם איז דורך לעוורידזשינג אַ געצייַג גערופֿן רעקורסיאָן, וואָס איז וואָס מיר רע געגאנגען צו זייַן גערעדט וועגן באַלד, אָבער מיר האָבן ניט טאַקע גערעדט וועגן נאָך. 

דאָ ס דער גרונט געדאַנק הינטער צונויפגיסן סאָרט. סאָרט די לינקס האַלב פון די מענגע, אַסומינג N איז גרעסער ווי 1. און וואָס איך מיינען ווען איך זאָגן אַסומינג N איז גרעסער ווי 1 איז, איך טראַכטן מיר קענען שטימען אַז אויב אַ מענגע בלויז באשטייט פון אַ איין עלעמענט, עס ס אויסגעשטעלט. מיר טאָן ניט אַקטשאַוואַלי דאַרפֿן צו טאָן עפּעס צו עס. מיר קענען נאָר דערקלערן עס צו זיין אויסגעשטעלט. עס ס נאָר אַ איין עלעמענט. 

אזוי די פּסעודאָקאָדע, ווידער, איז סאָרט די לינקס האַלב פון די מענגע, דעמאָלט סאָרט די רעכט האַלב די מענגע, דעמאָלט צונויפגיסן די צוויי כאַווז צוזאַמען. איצט, שוין איר זאל זיין טראכטן, עס מין פון נאָר סאָונדס ווי איר ניטאָ פּאַטינג אַוועק טהע-- איר ניטאָ ניט טאַקע טאן עפּעס. איר 'רע געזאגט סאָרט די לינקס האַלב, סאָרט די רעכט האַלב, אבער איר ניטאָ ניט טעלינג מיר ווי איר ניטאָ טאן עס. 

אבער געדענקען אַז ווי לאַנג ווי אַ מענגע איז אַ איין עלעמענט, מיר קענען דערקלערן עס אויסגעשטעלט. דעמאָלט מיר קענען נאָר פאַרבינדן זיי צוזאַמען. און אַז ס אַקשלי די פונדאַמענטאַל געדאַנק הינטער צונויפגיסן סאָרט, איז צו ברעכן עס אַראָפּ אַזוי אַז דיין ערייז זענען פון נומער איין. און דעמאָלט איר ריבילד פון דאָרט. 

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

אזוי מיר האָבן די זעלבע מענגע ווי די אנדערע סאָרטינג אַלגערידאַם ווידיאס אויב איר ווע געזען טהעמ-- אַ זעקס עלעמענט מענגע. און אונדזער פּסעודאָקאָדע קאָד דאָ איז סאָרט די לינקס האַלב, סאָרט די רעכט האַלב, צונויפגיסן די צוויי כאַווז צוזאַמען. אַזוי לאָזן ס נעמען דעם זייער טונקל ציגל רויט מענגע און סאָרט די לינקס האַלב פון עס. 

אַזוי פֿאַר די צייַט ווייל, מיר רע געגאנגען צו איגנאָרירן די שטאָפּן אויף די רעכט. עס ס דאָרט, אָבער מיר ניטאָ ניט אין אַז שריט נאָך. מיר ניטאָ ניט בייַ סאָרט די רעכט האַלב פון די מענגע. מיר ניטאָ בייַ סאָרט די לינקס האַלב פון די מענגע. און נאָר פֿאַר די צוליב פון ווייל אַ ביסל מער קלאָר, אַזוי איך קענען אָפּשיקן צו וואָס שריט מיר ניטאָ אויף, איך בין געגאנגען צו באַשטימען די קאָליר פון דעם סכום צו מאַראַנץ. איצט, מיר ניטאָ נאָך גערעדט וועגן די זעלביקער לינקס העלפט פון דער אָריגינעל מענגע. אבער איך בין כאָופּינג אַז דורך ווייל קענען צו אָפּשיקן צו די פֿאַרבן פון פאַרשידן זאכן, עס וועט מאַכן עס אַ ביסל מער קלאָר וואָס ס 'געגאנגען אויף דאָ. 

גוט, אַזוי איצט מיר האָבן אַ דרייַ עלעמענט מענגע. ווי טאָן מיר סאָרט די לינקס העלפט פון דעם מענגע, וואָס איז נאָך דעם שריט? מיר 'רע טריינג צו סאָרט די לינקס העלפט פון די ציגל רויט אַררייַ-- די לינקס האַלב פון וואָס איך ווע איצט בונט מאַראַנץ. 

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

און אַזוי איך בין געגאנגען צו זאָגן אַז די לינקס האַלב פון די לינקס האַלב די מענגע איז פּונקט דער עלעמענט פינף. פינף, ווייל אַ איין עלעמענט מענגע, מיר וויסן ווי צו סאָרט עס. און אַזוי פינף איז אויסגעשטעלט. מיר 'רע נאָר געגאנגען צו דערקלערן אַז. עס ס אַ איין עלעמענט מענגע. 

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

דאס איז איצט די ערשטער מאָל מיר ווע ריטשט אַ צונויפגיסן שריט. מיר האָבן געענדיקט, כאָטש מיר ניטאָ איצט מין פון נעסטעד דאָוונ-- און אַז ס סאָרט פון די טריקי זאַך מיט רעקורסיאָן איז, איר דאַרפֿן צו האַלטן דיין קאָפּ וועגן ווו מיר זענען. אַזוי מיר ווע סאָרט פון די לינקס העלפט פון דער מאַראַנץ חלק. 

און איצט, מיר ניטאָ אין דער מיטן פון סאָרטינג די רעכט העלפט פון דער מאַראַנץ חלק. און אין אַז פּראָצעס, מיר זענען איצט וועגן צו זיין אויף די שריט, צונויפגיסן די צוויי כאַווז צוזאַמען. ווען מיר קוקן אין די צוויי כאַווז פון די מענגע, מיר זען צוויי און איינער. וואָס עלעמענט איז קלענערער? איין. 

דעמאָלט וואָס עלעמענט איז קלענערער? נו, עס ס צוויי אָדער גאָרנישט. אַזוי עס ס צוויי. אַזוי איצט, נאָר צו ווידער ראַם ווו מיר זענען אין קאָנטעקסט, מיר האָבן אויסגעשטעלט די לינקס העלפט פון דער מאַראַנץ און די רעכט האַלב פון די אָנהייב. איך וויסן איך ווע געביטן די פֿאַרבן ווידער, אָבער אַז ס ווו מיר זענען. און די סיבה איך האט דעם איז ווייַל דעם פּראָצעס איז געגאנגען צו האַלטן געגאנגען, יטעראַטינג אַראָפּ. מיר ווע אויסגעשטעלט די לינקס העלפט פון די ערשטע מאַראַנץ און די רעכט האַלב פון די ערשטע מאַראַנץ. 

איצט, מיר דאַרפֿן צו צונויפגיסן די צוויי כאַווז צוזאַמען אויך. אַז ס די שריט מיר ניטאָ אויף. אַזוי מיר באַטראַכטן אַלע פון ​​די עלעמענטן וואָס זענען איצט גרין, די לינקס העלפט פון דער אָריגינעל מענגע. און מיר צונויפגיסן יענע ניצן די זעלבע פּראָצעס מיר האבן פֿאַר מערדזשינג צוויי און איינער נאָר אַ מאָמענט צוריק. 

די לינקס העלפט, דער קלענסטער עלעמענט אויף די לינקס העלפט איז פינף. דער קלענסטער עלעמענט אויף די רעכט העלפט איז איינער. וואָס פון די איז קלענערער? איין. 

דער קלענסטער עלעמענט אויף די לינקס העלפט איז פינף. דער קלענסטער עלעמענט אויף די רעכט העלפט איז צוויי. וואָס ס דער קלענסטער? צוויי. און דעמאָלט לאַסטלי פינף און גאָרנישט, מיר קענען זאָגן פינף. 

גוט, אַזוי גרויס בילד, לאָזן ס נעמען אַ ברעכן פֿאַר אַ רגע און רעכענען אויס ווו מיר זענען. אויב מיר סטאַרטעד פֿון די זייער אָנהייב, מיר האָבן איצט געענדיקט פֿאַר די קוילעלדיק מענגע נאָר איין שריט פון די פּסעודאָקאָדע קאָד דאָ. מיר האָבן אויסגעשטעלט די לינקס האַלב פון די מענגע. 

ריקאָל אַז דער אָריגינעל סדר איז געווען פינף, צוויי, איינער. דורך געגאנגען דורך דעם פּראָצעס און נעסטינג אַראָפּ און ריפּיטינג, ממשיך צו ברעכן די פּראָבלעם אַראָפּ אין קלענערער און קלענערער פּאַרץ, מיר האָבן איצט געענדיקט שריט איינער פון די פּסעודאָקאָדע פֿאַר די גאנצע סטאַרטינג מענגע. מיר האָבן אויסגעשטעלט זייַן לינקס האַלב. 

אַזוי איצט לאָזן ס פרירן עס. און איצט לאָזן ס סאָרט די רעכט העלפט פון דער אָריגינעל מענגע. און מיר רע געגאנגען צו טאָן אַז דורך געגאנגען דורך די זעלבע יטעראַטיווע פּראָצעס פון ברייקינג זאכן אַראָפּ און דעמאָלט מערדזשינג זיי צוזאַמען. 

אזוי די לינקס העלפט פון די רויט, אָדער די לינקס העלפט פון די רעכט האַלב פון דער אָריגינעל מענגע, איך בין געגאנגען צו זאָגן איז דרייַ. ווידער, איך בין ווייל קאָנסיסטענט דאָ. אויב איר האָבן אַ מאָדנע נומער פון עלעמענטן, עס טוט ניט טאַקע ענין צי איר מאַכן די לינקס איינער קלענערער אָדער די רעכט איינער קלענערער. 

וואָס ענינים איז אַז ווען איר טרעפן דעם פּראָבלעם אין קאַנדאַקטינג אַ צונויפגיסן, איר דאַרפֿן צו זייַן קאָנסיסטענט. איר אָדער שטענדיק דאַרפֿן צו מאַכן אַ לינקס זייַט קלענערער אָדער שטענדיק דאַרפֿן צו מאַכן די רעכט זייַט קלענערער. דאָ, איך ווע אויסדערוויילט צו שטענדיק מאַכן די לינקס זייַט קלענערער ווען מיין מענגע, אָדער מיין סאַב-מענגע, איז פון אַ מאָדנע נומער. 

דריי איז אַ איין עלעמענט, און אַזוי עס איז אויסגעשטעלט. מיר ווע לעוועראַגעד אַז האַשאָרע איבער אונדזער גאנצע פּראָצעס אַזוי ווייַט. אַזוי איצט לאָזן ס סאָרט די רעכט העלפט פון די רעכט העלפט, אָדער די רעכט האַלב פון די רויט. 

ווידער, מיר דאַרפֿן צו שפּאַלטן דעם אַראָפּ. דאס איז ניט אַ איין עלעמענט מענגע. מיר קענען ניט דערקלערן עס אויסגעשטעלט. און אַזוי ערשטער, מיר רע געגאנגען צו סאָרט די לינקס האַלב. 

די לינקס העלפט איז אַ איין עלעמענט, אַזוי עס ס סאָרט פון דורך ניט ויסצאָלן. דעמאָלט מיר רע געגאנגען צו סאָרט די רעכט העלפט, וואָס איז אַ איין עלעמענט. עס ס אויסגעשטעלט דורך ניט ויסצאָלן. און איצט, מיר קענען צונויפגיסן די צוויי צוזאַמען. פיר איז קלענערער, ​​און דעמאָלט זעקס איז קלענערער. 

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

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

אַזוי איצט מיר קענען צונויפגיסן יענע צוויי כאַווז צוזאַמען. און אַז ס וואָס מיר טאָן דאָ. אזוי די שוואַרץ שורה נאָר צעטיילט די לינקס העלפט און די רעכט האַלב פון דעם סאָרט טייל. 

מיר פאַרגלייַכן די קלענסטער ווערט אויף די לינקס זייַט פון די אַררייַ-- אָדער אַנטשולדיקן מיר, דער קלענסטער ווערט פון די לינקס האַלב צו דער קלענסטער ווערט פון די רעכט האַלב און געפינען אַז דרייַ איז קלענערער. און איצט אַ ביסל פון אַ אַפּטאַמאַזיישאַן, רעכט? עס ס אַקטשאַוואַלי גאָרנישט לינקס אויף די לינקס זייַט. 

עס ס גאָרנישט רוען אויף די לינקס זייַט, אַזוי מיר קענען עפפיסיענטלי נאָר מאָווע-- מיר קענען דערקלערן די מנוחה פון עס איז אַקטשאַוואַלי אויסגעשטעלט און נאָר שטיפט עס אויף, ווייַל עס ס גאָרנישט אַנדערש צו פאַרגלייַכן קעגן. און מיר וויסן אַז די רעכט זייַט פון די רעכט זייַט איז אויסגעשטעלט. 

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

אַזוי איצט, אַלע וואָס בלייבט איז פֿאַר אונדז צו צונויפגיסן די צוויי כאַווז צוזאַמען. אַזוי מיר פאַרגלייַכן די לאָואַסט וואַליוד עלעמענט פון יעדער העלפט פון די מענגע אין דרייען און גיינ ווייַטער. איינער איז ווייניקער ווי דרייַ, אַזוי איינער גייט. 

צוויי איז ווייניקער ווי דרייַ, אַזוי צוויי גייט. דריי איז ווייניקער ווי 5, אַזוי דרייַ גייט. פיר איז ווייניקער ווי 5, אַזוי פיר גייט. דעמאָלט פינף איז ווייניקער ווי זעקס, און זעקס איז אַלע אַז בלייבט. 

איצט, איך וויסן, וואָס איז געווען אַ פּלאַץ פון טריט. און מיר ווע לינקס אַ פּלאַץ פון זיקאָרן אין אונדזער וועקן. און אַז ס וואָס די גרוי סקווערז זענען. און עס מיסטאָמע פּעלץ ווי אַז גענומען אַ פּלאַץ מער ווי ינסערשאַן סאָרט, בלאָז סאָרט, אָדער סעלעקציע סאָרט. 

אבער אַקטשאַוואַלי, ווייַל אַ פּלאַץ פון די פּראַסעסאַז זענען געשעעניש אין דער זעלביקער טימע-- וואָס איז עפּעס מיר וועט, ווידער, רעדן וועגן ווען מיר רעדן וועגן רעקורסיאָן אין אַ צוקונפֿט ווידעאָ-- דעם אַלגערידאַם אַקטשאַוואַלי קלאר איז פונדאַמענטאַללי אַנדערש ווי עפּעס מיר האָבן געזען איידער אָבער איז אויך באטייטיק מער עפעקטיוו. 

וואָס איז וואָס? נו, אין די ערגסטע פאַל סצענאַר, מיר האָבן צו שפּאַלטן N עלעמענטן זיך און דעמאָלט רעקאָמבינע זיי. אבער ווען מיר רעקאָמבינע זיי, וואָס מיר ניטאָ טאן איז בייסיקלי דאַבלינג די גרייס פון דער קלענערער ערייז. מיר האָבן אַ בינטל פון איין עלעמענט ערייז אַז מיר Effectively פאַרבינדן אין צוויי עלעמענט ערייז. און דעמאָלט מיר נעמען די צוויי עלעמענט ערייז און פאַרבינדן זיי צוזאַמען אין פיר עלעמענט ערייז, און אַזוי אויף, און אַזוי אויף, און אַזוי אויף, ביז מיר האָבן אַ איין N עלעמענט מענגע. 

אבער ווי פילע דאָובלינגס טוט עס נעמען צו באַקומען צו N? טראַכטן צוריק צו דער טעלעפאָנירן בוך בייַשפּיל. ווי פילע מאל טאָן מיר האָבן צו טרער די טעלעפאָנירן בוך אין האַלב, ווי פילע מער מאל טאָן מיר האָבן צו טרער די טעלעפאָנירן בוך אין האַלב, אויב די נומער פון די טעלעפאָנירן בוך דאַבאַלד? עס ס נאָר איין, רעכט? 

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

אַזוי אין דער בעסטער פאַל און אין די ערגסט פאַל, דעם אַלגערידאַם ראַנז אין N קלאָץ N צייַט. מערדזש סאָרט איז באשטימט אַ ביסל טריקיער ווי די אנדערע הויפּט סאָרטינג אַלגערידאַמז מיר ווע גערעדט וועגן קס50 אָבער איז סאַבסטאַנשאַלי מער שטאַרק. 

און אַזוי אויב איר אלץ געפינען געלעגנהייַט צו דאַרפֿן עס אָדער צו נוצן עס צו סאָרט אַ גרויס דאַטן שטעלן, געטינג דיין קאָפּ אַרום דעם געדאַנק פון רעקורסיאָן איז געגאנגען צו זיין טאַקע שטאַרק. און עס ס געגאנגען צו מאַכן דיין מגילה טאַקע פיל מער עפעקטיוו ניצן צונויפגיסן סאָרט קעגן עפּעס אַנדערש. איך בין דאַג לויד. דאס איז קס50.