[موسیقی] 

داگ لوید: خوب، پس یک ادغام مرتب سازی بر اساس الگوریتم هنوز یکی دیگر از که ما می توانیم به مرتب کردن استفاده عناصر یک آرایه. اما همانطور که خواهیم دید، آن را به یک تفاوت بسیار اساسی از مرتب سازی انتخابی، حباب مرتب کردن، و مرتب سازی درجی که آن را واقعا خیلی هوشمندانه. 

ایده اصلی در پشت ادغام مرتب سازی بر است برای مرتب کردن آرایه های کوچکتر و سپس ترکیب آن آرایه با هم، و یا ادغام them-- از این رو در name-- مرتب شده اند. راه که ادغام مرتب سازی بر کند این است با اعمال نفوذ یک ابزار به نام بازگشت، آن چیزی است که ما در حال رفتن به صحبت کردن در مورد به زودی، اما ما واقعا در مورد هنوز صحبت نمی کند. 

در اینجا ایده اصلی در پشت مرتب سازی بر ادغام است. مرتب کردن بر اساس نیمه سمت چپ از آرایه، فرض n بزرگتر از 1 است. و آنچه که من وقتی می گویم فرض n بزرگتر از 1 است، من فکر می کنم ما می توانیم که اگر یک آرایه تنها متشکل از یک عنصر، آن طبقه بندی شده اند. ما در واقع لازم نیست برای انجام هر کاری به آن است. ما فقط می تواند اعلام آن را به طبقه بندی شده اند. این تنها یک عنصر است. 

بنابراین شبه دوباره است، مرتب کردن بر اساس نیمه سمت چپ آرایه، سپس به ترتیب در نیمه سمت راست آرایه، پس از آن با هم ادغام دو نیمه. در حال حاضر، در حال حاضر شما ممکن است فکر کردن، آن هم از نوع فقط برای تلفن های موبایل مانند شما در حال قرار دادن the-- شما در واقع انجام هر چیزی نیست. شما می گویید مرتب سازی بر اساس سمت چپ نیم، مرتب کردن بر اساس نیمه سمت راست، اما شما در حال گفتن نیست من چگونه شما آن را انجام می دهند. 

اما به یاد داشته باشید که تا زمانی که یک آرایه یک عنصر است، ما می تواند اعلام آن طبقه بندی شده اند. سپس ما فقط می توانید آنها را با هم ترکیب. و این در واقع ایده اساسی که پشت مرتب سازی بر ادغام، است به شکستن آن به طوری که آرایه های خود را از اندازه یکی هستند. و سپس شما را از وجود دارد را بازسازی کند. 

مرتبسازی ادغامی است که قطعا یک الگوریتم پیچیده است. و آن را نیز کمی پیچیده به تجسم. پس امیدوارم، تجسم که من در اینجا به شما کمک خواهد به دنبال همراه. و من سعی کنید بهترین من به روایت همه چیز و ادامه طریق این کمی بیشتر به آرامی از آنهایی که دیگر فقط به امید گرفتن سر خود را در اطراف ایده پشت مرتب سازی بر ادغام. 

بنابراین ما باید آرایه همان فیلم های دیگر الگوریتم مرتب سازی اگر شما را دیده ام them-- یک آرایه شش عنصر است. و کد شبه ما در اینجا این است مرتب سازی بر نیمه چپ، مرتب کردن نیمه سمت راست، با هم ادغام دو نیمه. بنابراین اجازه دهید این آجر قرمز بسیار تاریک آرایه و مرتب کردن نیمه سمت چپ آن است. 

بنابراین در حال حاضر، ما قصد داریم به چشم پوشی از مسائل در سمت راست. آن وجود دارد، اما ما که در آن گام نشده است. ما نه در مرتب کردن بر اساس نیمه راست آرایه. ما در مرتب سازی بر سمت چپ هستید نیمی از آرایه. و فقط به خاطر بودن کمی بیشتر روشن است، بنابراین من می توانید مراجعه کنید به چه مرحله ما در آن هستید، من قصد دارم برای تغییر رنگ این مجموعه به رنگ نارنجی. در حال حاضر، ما در حال صحبت کردن در هنوز هم در مورد نیمه سمت چپ همان آرایه اصلی. اما من امیدوار است که قادر بودن به به رنگ از آیتم های مختلف مراجعه کنید، آن را آن را کمی بیشتر را روشن چه خبر است اینجا. 

OK، بنابراین در حال حاضر ما یک سه عنصر آرایه. چگونه نیمه سمت چپ این که ما مرتب سازی بر اساس آرایه، که هنوز هم این مرحله؟ ما در حال تلاش برای مرتب کردن سمت چپ نیمی از آجر قرمز آرایه نیمه سمت چپ که من در حال حاضر رنگ نارنجی است. 

خب، ما می تواند امتحان کنید و دوباره این روند را تکرار. بنابراین ما هنوز هم در حال وسط تلاش برای نیمه چپ آرایه کامل. نیمه سمت چپ از آرایه، من فقط رفتن به خودسرانه تصمیم می گیرید که نیمه سمت چپ کوچکتر از نیمه سمت راست خواهد بود، چرا که این اتفاق می افتد به شامل سه عنصر است. 

و به این ترتیب من قصد دارم به می گویند که نیمه چپ نیمه سمت چپ آرایه فقط پنج عنصر است. پنج، که یک عنصر آرایه، ما می دانیم چگونه به آن را مرتب. و به این ترتیب پنج طبقه بندی شده اند است. ما فقط قصد داریم تا اعلام کند که. این یک آرایه عنصر است. 

بنابراین ما در حال حاضر طبقه بندی شده اند ام نیمه چپ چپ half-- و یا نه، ما طبقه بندی شده اند ام نیمه سمت چپ نارنجی. بنابراین در حال حاضر، به منظور هنوز هم کامل نیمه چپ آرایه کلی است، ما نیاز به مرتب کردن نیمه سمت راست از نارنجی، و یا این مسائل. چگونه ما انجام این کار؟ خب، ما باید یک آرایه دو عنصر است. بنابراین ما می توانیم نیمه سمت چپ مرتب سازی بر اساس از آرایه است، که دو. دو یک عنصر است. پس از آن به طور پیش فرض طبقه بندی شده اند. پس ما می توانیم در نیمه سمت راست مرتب سازی بر اساس آن بخش از آرایه، یک. که مرتب سازی بر اساس پیش فرض. 

این در حال حاضر اولین بار ما یک قدم ادغام رسیدهاید. ما را تکمیل کرده اند، اگر چه ما در حال حاضر از نوع تو در تو down-- و آن نوع از روی حیله و تزویر است چیزی که با بازگشتی است شما نیاز به نگه داشتن خود را سر در مورد که در آن ما هستند. بنابراین ما به نوعی از سمت چپ نیمی از بخش نارنجی. 

و اکنون، ما در وسط مرتب سازی هستید نیمه راست بخش نارنجی. و در این فرآیند، ما در حال حاضر حدود به گام باشد، با هم ادغام دو نیمه. هنگامی که ما در دو نیمه نگاه از آرایه، ما دو و یک را ببینید. کدام عنصر کوچکتر است؟ یکی. 

پس از آن که عنصر کوچکتر است؟ خوب، آن را دو یا هیچ چیز نیست. پس از آن دو. بنابراین در حال حاضر، فقط به دوباره قاب که در آن ما در زمینه هستند، ما مرتب سازی بر حسب نیمه سمت چپ نارنجی و نیمه سمت راست از مبدا. من می دانم من رنگ را تغییر داده ام دوباره، اما این که در آن ما بود. و به همین دلیل من این است چرا که این فرآیند است رفتن به رفتن ادامه، تکرار است. ما در سمت چپ طبقه بندی شده اند که نیمی از پرتقال سابق و نیمه سمت راست از رنگ نارنجی سابق. 

در حال حاضر ما نیاز به ادغام آن دو نیمه با هم بیش از حد. که گام ما در هستیم. بنابراین ما همه از نظر عناصر که در حال حاضر سبز، نیمه چپ آرایه اصلی. و کسانی را ادغام استفاده از روند مشابه ما برای ادغام دو بود و یکی فقط یک لحظه پیش. 

نیمه چپ، کوچکترین عنصر در نیمه سمت چپ و پنج است. کوچکترین عنصر در در نیمه سمت راست است. کدام یک از این کوچکتر است؟ یکی. 

کوچکترین عنصر در نیمه سمت چپ و پنج است. کوچکترین عنصر در در نیمه سمت راست دو است. چه کوچکترین خبر؟ دو. و سپس در آخر پنج و هیچ چیز، ما می توانیم پنج گویند. 

OK، تصویر بسیار بزرگ، اجازه دهید استراحت برای یک ثانیه و کشف کردن که در آن ما هستند. اگر ما از آغاز همان ابتدا، ما در حال حاضر برای تکمیل آرایه به طور کلی فقط یک قدم از کد شبه در اینجا. ما طبقه بندی شده اند کرده اند نیمه سمت چپ آرایه. 

به یاد بیاورید که اصلی سفارش پنج، دو، یک بود. رفتن را از طریق این فرآیند و تودرتو و تکرار، در ادامه به شکستن مشکل را به قطعات کوچکتر و کوچکتر، ما در حال حاضر به اتمام مرحله یکی از شبه برای کل آرایه شروع. ما نیمه چپ آن طبقه بندی شده اند. 

بنابراین در حال حاضر مسدود است. و اکنون اجازه دهید در سمت راست مرتب سازی بر اساس نیمی از آرایه اصلی است. و ما قصد داریم به این کار را با رفتن را از طریق تکرار همان روند شکستن همه چیز و سپس آنها را ادغام با هم. 

بنابراین نیمه سمت چپ قرمز، و یا نیمه سمت چپ از نیمه سمت راست از اصلی آرایه، من قصد دارم به سه است. باز هم، من سازگار بودن در اینجا. اگر شما یک فرد تعدادی از عناصر آن، واقعا مهم نیست که آیا شما را به سمت چپ کوچکتر و یا یک حق کوچکتر است. 

مهم این است که هر زمان که شما این مشکل روبرو می شوند در انجام ادغام، شما نیاز به سازگار است. شما هم همیشه نیاز به یک سمت چپ کوچکتر و یا همیشه نیاز به در سمت راست کوچکتر است. در اینجا، من برای همیشه انتخاب کرده اید را در سمت چپ کوچکتر وقتی آرایه من، یا من زیر آرایه است، از اندازه عجیب و غریب. 

سه یک عنصر است، و پس از آن طبقه بندی شده اند است. ما این فرضیه را قوی تر در سراسر کل فرآیند ما تا کنون. پس به سمت راست مرتب سازی بر اساس نیمی از نیمه سمت راست، و یا نیمه سمت راست از رنگ قرمز است. 

باز هم، ما نیاز به تقسیم این پایین. این یک آرایه عنصر است. ما نمی توانیم اعلام آن به طبقه بندی شده اند. و به این ترتیب برای اولین بار، ما قصد داریم مرتب سازی بر اساس نیمه سمت چپ. 

نیمه چپ یک عنصر است، پس از آن نوع به طور پیش فرض. سپس ما قصد داریم برای مرتب کردن سمت راست نیمه است، که یک عنصر واحد. آن را به طور پیش فرض طبقه بندی شده اند. و در حال حاضر، ما می توانیم آن دو با هم ادغام خواهند شد. چهار کوچکتر است، و سپس شش کوچکتر است. 

باز هم، آنچه را که ما در این نقطه انجام می شود؟ ما در سمت چپ طبقه بندی شده اند که نیمی از نیمه سمت راست. و یا رفتن به اصلی رنگ هایی که وجود دارد، ما در سمت چپ طبقه بندی شده اند که نیمی از قرمز نرمتر است. این در اصل یک آجر تاریک قرمز و در حال حاضر آن را به یک نرم تر قرمز، و یا آن را به یک قرمز نرمتر بود. 

و سپس ما طبقه بندی شده اند ام نیمه راست قرمز نرمتر است. در حال حاضر، خوب، آنها دوباره سبز هستید، فقط چون ما قصد از طریق یک فرایند. و ما مجبور به تکرار این بارها و بارها. 

بنابراین در حال حاضر ما می توانیم آن ادغام دو نیمه با هم. و این چیزی است که ما در اینجا انجام. به طوری که خط سیاه و سفید فقط نیمه چپ تقسیم و نیمه سمت راست این بخش مرتب سازی بر. 

ما به مقایسه کوچکترین مقدار در سمت چپ از آرایه و یا ببخشید، کوچکترین ارزش نیمه سمت چپ به کوچکترین ارزش سمت راست نیمه و پیدا کردن که سه کوچکتر است. و در حال حاضر یک بیت از یک بهینه سازی، درست است؟ در واقع وجود دارد هیچ چیز در سمت چپ در سمت چپ. 

هیچ چیز باقی مانده وجود دارد در سمت چپ، بنابراین ما کارآمد می تواند فقط move-- ما می تواند اعلام بقیه از آن است که در واقع طبقه بندی شده اند و فقط آن را رویه ، چرا که هیچ چیز وجود دارد دیگری برای مقایسه با و ما می دانیم که در سمت راست از سمت راست طبقه بندی شده اند است. 

خوب، پس حالا بیایید دوباره منجمد و شکل که در آن ما در داستان هستند. در آرایه به طور کلی، چه انجام دهیم؟ ما در واقع انجام در حال حاضر یکی و گام به گام دو مرحله است. ما طبقه بندی شده اند در نیمه سمت چپ، و ما در نیمه سمت راست طبقه بندی شده اند. 

بنابراین در حال حاضر، که باقی می ماند این است که برای ما به ادغام این دو نیمه با هم. بنابراین ما به مقایسه کمترین ارزش عنصر هر نیمی از آرایه به نوبه خود و ادامه دهید. یکی کمتر از سه است، بنابراین یک می رود. 

دو کمتر از سه است، بنابراین دو می رود. سه کمتر از 5 است، پس از سه رود. چهار کمتر از 5 است، بنابراین چهار می رود. پس از آن پنج کمتر از شش است، و شش است که باقی می ماند. 

در حال حاضر، من می دانم، که بسیاری از مراحل بود. و ما بسیاری را ترک کرده ام حافظه در پی ما است. و این چیزی است که کسانی که مربع خاکستری هستند. و آن را احتمالا احساس که در زمان بسیاری دیگر از مرتب سازی بر درج، حباب مرتب سازی بر اساس، و یا انتخاب نوع. 

اما در واقع، به دلیل بسیاری از این فرآیندها ها در همان اتفاق می افتد time-- چیزی خواهیم که، دوباره، صحبت در مورد زمانی که ما در مورد صحبت بازگشت در آینده video-- این الگوریتم در واقع به وضوح اساسا متفاوت از هر چیزی ما دیده اند، قبل اما همچنین به طور قابل توجهی کارآمدتر. 

چرا چنین است؟ خب، در بدترین سناریو مورد، ما به تقسیم n عنصر تا و سپس آنها را ترکیب. اما زمانی که ما ترکیب آنها، آنچه ما انجام می است که اساسا دو برابر شدن اندازه آرایه کوچکتر است. ما یک دسته از یک عنصر آرایه که ما به طور موثر ترکیب را به دو آرایه عنصر. و سپس ما آن را دو آرایه عنصر و آنها را با هم ترکیب را به چهار رشته عنصر، و غیره، و غیره، و غیره، تا زمانی که ما باید یک آرایه از عناصر N است. 

اما چگونه بسیاری از دوبرابر شدن آن را برای رسیدن به N؟ فکر می کنم به عنوان مثال دفترچه تلفن. چند بار ما باید به پاره دفترچه تلفن در نیمه، که چگونه بسیاری از بار ما باید به پاره دفترچه تلفن در نیم، اگر به اندازه دفترچه تلفن دو برابر؟ فقط یک وجود دارد، درست است؟ 

بنابراین برخی از مرتب کردن بر اساس وجود دارد عنصر لگاریتمی است. اما ما نیز هنوز به حداقل در همه عناصر N نگاه کنید. بنابراین در بدترین حالت، مرتبسازی ادغامی در n log n استفاده می کند. ما به در نگاه کنید همه عناصر ازت، و ما باید آنها را ترکیب ورود به سیستم با هم در N مجموعه ای از مراحل. در بهترین حالت، آرایه کاملا طبقه بندی شده اند. عالیه. اما بر اساس الگوریتم ما را در اینجا، ما هنوز به تقسیم و ترکیب. اگر چه در این مورد، بازترکیب نوع بی اثر است. این مورد نیاز است. اما ما هنوز هم از طریق رفتن کل فرایند به هر حال. 

بنابراین در بهترین حالت و در بدترین حالت، این الگوریتم را اجرا می کند در n log n استفاده می شود. مرتبسازی ادغامی است که قطعا یک کمی سختتر از دیگر الگوریتم های مرتب سازی اصلی ما در مورد CS50 صحبت کردیم اما قابل ملاحظه ای قوی تر است. 

و بنابراین اگر شما همیشه پیدا مناسبت به آن نیاز دارید و یا استفاده از آن برای مرتب کردن بر اساس مجموعه بزرگ داده ها، گرفتن سر خود را در اطراف این ایده از بازگشت در حال رفتن به واقعا قدرتمند است. و آن را به خود برنامه های واقعا بسیار کارآمد تر با استفاده از ادغام مرتب سازی بر در مقابل هر چیز دیگری. من داگ لوید هستم. این CS50 است.