[Powered by Google Translate] [מערדזש סאָרט] [ראָב באָוודען - האַרוואַרד אוניווערסיטעט] [דאס איז קס50. - CS50.TV] זאל ס רעדן וועגן צונויפגיסן סאָרט. אַזוי ווייַט איר ווע געזען בלאָז סאָרט, ינסערשאַן סאָרט, און סעלעקציע סאָרט. כאָטש איך וועט מין פון כוואַליע מיין האַנט אין וואָס איך מיינען דורך בעסער, צונויפגיסן סאָרט בכלל פּערפאָרמז בעסער ווי קיין פון די 3 סאָרץ. 

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

בשעת דעם אַרבעט, עס ס אַ פּלאַץ פון ומנייטיק אַרבעט. מיר קענען טאָן עס פאַסטער ווי נאָר סאָרטינג. נאָטיץ אַז איינער אומרעכט געדאַנק איז צו נאָר נעמען אָלטערנייטינג טעפּלעך פון יעדער רשימה. בשעת אַז קען ויסקומען ווי וואָס אַרבעט בייַ ערשטער, טאן אַז מיר סוף אַרויף מיט 4, 8, 15, 23, 16 - באַמערקן אַז 16 און 23 זענען אויס פון אָרט. דאס איז ווייַל 2 עלעמענטן וואָס זאָל דערשייַנען קאָנסעקוטיווע אין די מערדזשד רשימה זענען אין די זעלבע ערשט רשימה. ביידע 15 און 16 זענען אין די רשימה אויף די לינקס. דער קונץ איז צו נעמען מייַלע פון ​​די פאַקט אַז ביידע רשימות זענען שוין אויסגעשטעלט. דאס מיטל אַז אויב מיר נאָר קוק אין דער ערשטער עלעמענטן פון ביידע רשימות - דאָ, 4 און 8 - איינער פון זיי מוזן אויך זייַן דער ערשטער עלעמענט פון דער מערדזשד רשימה. נו, וואָס איז וואָס? ביידע פון ​​די רשימות זענען שוין אויסגעשטעלט, און אַזוי אָדער 4 אָדער 8 מוזן זייַן דער קלענסטער עלעמענט ווען מיר פאַרבינדן די 2 רשימות. אין דעם פאַל, די קלענסטער איז 4, אַזוי מיר קענען נעמען אויס 4 און מאַכן עס דער ערשטער עלעמענט פון אונדזער מערדזשד רשימה. איצט מיר פאָרזעצן מערדזשינג די רוען 3 יסודות פון דער ערשטער רשימה און 4 יסודות פון די רגע רשימה. 

אַמאָל ווידער, מיר נאָר דאַרפֿן צו קוקן אין די ערשטער עלעמענט פון ביידע רשימות. דער קלענערער פון די 2 מוזן זייַן די רגע עלעמענט פון אונדזער מערדזשד רשימה. דאס מאָל, צווישן 8 און 15 דער קלענסטער איז 8, און אַזוי מיר אַרייַנלייגן אַז ווי די רגע עלעמענט פון אונדזער אויסגעשטעלט רשימה. מיר קענען פאָרזעצן קאַמפּערינג דער ערשטער עלעמענטן פון ביידע רשימות און רימוווינג דער קלענערער פון די 2. קאַמפּערינג 15 און 23, 15 איז קלענערער און אַזוי אַז ס אונדזער דריט עלעמענט. איצט קאַמפּערינג 16 און 23, 16 איז קלענערער. אַזוי אַז ס דער פערט עלעמענט. 

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

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

און איצט מיר האָבן 8 רשימות מיט אַ איין גלעזל אין יעדער רשימה. אַזוי אַז ס עס פֿאַר שריט 1. פֿאַר שריט 2, מיר ריפּיטידלי צונויפגיסן פּערז פון רשימות ניצן די צונויפגיסן אַלגערידאַם מיר געלערנט פריער. מערדזשינג 108 און 15, מיר סוף אַרויף מיט דער רשימה 15, 108. מערדזשינג 50 און 4, מיר סוף אַרויף מיט 4, 50. מערדזשינג 8 און 42, מיר סוף אַרויף מיט 8, 42. און מערדזשינג 23 און 16, מיר סוף אַרויף מיט 16, 23. איצט אַלע אונדזער רשימות זענען פון גרייס 2. נאָטיץ אַז יעדער פון די 4 רשימות איז אויסגעשטעלט. 

אַזוי מיר קענען אָנהייבן מערדזשינג פּערז פון רשימות ווידער. מערדזשינג 15 און 108 און 4 און 50 - ערשטער נעמען די 4, דעמאָלט דער 15, דעמאָלט דער 50, דעמאָלט די 108. מערדזשינג 8, 42 און 16, 23, מיר ערשטער נעמען די 8, דעמאָלט דער 16, דעמאָלט דער 23, דעמאָלט דער 42. אַזוי איצט מיר האָבן נאָר 2 רשימות פון נומער 4, יעדער פון וואָס איז אויסגעשטעלט. אַזוי איצט מיר צונויפגיסן די 2 רשימות. ערשטער מיר נעמען די 4. דעמאָלט מיר נעמען די 8. דעמאָלט מיר נעמען די 15 און 16, דעמאָלט 23, דעמאָלט 42, דעמאָלט 50, דעמאָלט 108. און מיר רע געטאן. מיר איצט האָבן אַ אויסגעשטעלט רשימה. אַזוי ווי שנעל איז געווען דאָס, פּונקט? אין טעכניש תּנאָים, צונויפגיסן סאָרט איז אָ (N קלאָץ ען), וועראַז אַלע פון ​​בלאָז סאָרט, ינסערשאַן סאָרט, און סעלעקציע סאָרט ביסט אָ (N ²). אין פאַקט, ווי איר וועט לערנען באַלד, איר וועט נישט זייַן ביכולת צו קומען אַרויף מיט אַ סאָרט אַז פּערפאָרמז בעסער ווי אָ (N קלאָץ N) אין די אַלגעמיינע פאַל. ווידער, טאָן ניט זאָרג וועגן דעם גרויס אָ נאָוטיישאַן אויב איר האָט ניט געזען עס נאָך. 

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

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

מייַן נאָמען איז ראָב באָוודען, און דאָס איז קס50. [CS50.TV] - און סעלעקציע סאָרט. [לאַפס] אָה, גאַט צו נעמען אַז אויס אויך ווייַל איך סוויטשט ווי איך איז געווען פּריזענטינג עס. רשימה אויף די לינקס. וואָס איז געווען אַ טייפּאָו. [מיספּאָוק] איך סקרוד אַרויף - [לאַפס] איך טאָן ניט וויסן וואָס -