[সঙ্গীত বাজাচ্ছি] 

ডগ লয়েড: ঠিক আছে, তাই একটি একত্রীকরণ সাজান আরেকটা এলগরিদম আমরা বাছা করতে ব্যবহার করতে পারেন একটি অ্যারের উপাদান. হিসাবে আমরা দেখতে পাবেন, তবে তা পেয়েছিলাম একটি খুব মৌলিক পার্থক্য নির্বাচন সাজানোর, বুদ্বুদ থেকে সাজান, সন্নিবেশ এবং সাজানোর এটা সত্যিই বেশ চালাক না. 

একত্রিতকরণ পিছনে উপজীব্য সাজান ছোট অ্যারে বাছাই করা হয় এবং তারপর যারা অ্যারে একত্রিত একসাথে, বা them-- একত্রীকরণ অত: পর এ আদেশ অনুসারে সাজানো name--. সাজান আছে একত্রীকরণ যে ভাবে এই একটি টুল উপজীব্য করে হয় যা কি, recursion নামক আমরা শীঘ্রই কথা বলা ঠিক হবে চলুন কিন্তু সত্যিই কি আমরা এখনো সম্পর্কে কথা বলি নি. 

একত্রীকরণ এখানে সাজানোর পিছনে মৌলিক ধারণা. , অ্যারের বাম অর্ধেক বাছাই এন অভিমানী 1 তার চেয়ে অনেক বেশী. এবং আমি বলতে যখন কি মানে এন অভিমানী 1 তুলনায় বেশী, আমি মনে করি আমরা একমত হতে পারে মনে করেন যে একটি অ্যারের যদি শুধুমাত্র একটি একক উপাদান নিয়ে গঠিত, এটা সাজানো. আমরা আসলে প্রয়োজন হবে না এটা কিছু করতে. আমরা শুধু এটা সাজানো হতে ঘোষণা করা যেতে পারে. এটা শুধুমাত্র একটি একক উপাদান. 

সুতরাং pseudocode, আবার হয় , অ্যারের বাম অর্ধেক বাছাই তারপর ডান অর্ধেক অ্যারের সাজাতে, তারপর একসঙ্গে দুটি আংশিক একত্রীকরণ. এখন, ইতিমধ্যে আপনি হতে পারে চিন্তা, এটা কোন ধরনের মাত্র the-- আপনি বন্ধ নির্বাণ করছি মত শোনাচ্ছে আপনি আসলে কিছু করছেন না. আপনি বাম বাছা বলছে অর্ধেক, ডান অর্ধেক বাছাই, কিন্তু আপনি বলছ না আমার কিভাবে আপনি তা করছেন. 

কিন্তু যতদিন মনে রাখবেন একটি অ্যারের একটি একক উপাদান, আমরা এটা সাজানো ঘোষণা করতে পারেন. তারপর আমরা শুধু একসাথে তাদের একত্রিত করতে পারেন. এবং যে আসলে কী একত্রীকরণ সাজানোর পিছনে মৌলিক ধারণা, যাতে তা ভেঙ্গে দিতে হয় আপনার অ্যারে আকার এক হয়. এবং তারপর আপনি সেখানে থেকে পুনর্নির্মাণের. 

সাজান তা হ 'ল মার্জ একটি জটিল এলগরিদম. এবং এটি একটি সামান্য ঠাহর করা জটিল. তাই আশা করছি, কল্পনা যে আমি আপনি বরাবর অনুসরণ করতে সাহায্য করবে এখানে আছে. এবং আমি কিছু বর্ণনা করতে আমার ভাল করার চেষ্টা করব এবং এই একটি সামান্য আরো মাধ্যমে এগিয়ে ধীরে ধীরে অন্যান্য বেশী আশাকরি আপনার মাথা পেতে একত্রীকরণ সাজানোর পিছনে ধারণা কাছাকাছি. 

সুতরাং আমরা হিসাবে একই অ্যারে আছে অন্যান্য বাছাই আলগোরিদিম ভিডিও আপনি দেখা করেছি তাহলে them-- একটি ছয় উপাদান অ্যারের. এবং এখানে আমাদের pseudocode কোড সাজান হয় বাম অর্ধেক, ডান অর্ধেক বাছাই, একসঙ্গে দুই আংশিক একত্রীকরণ. তাই আসুন এই খুব অন্ধকার ইটের লাল নেওয়া যাক অ্যারে এবং এটি বাম অর্ধেক বাছাই. 

কিছু সময়ের জন্য তাই, আমরা চলুন ডানদিকে স্টাফ উপেক্ষা করা. এটা আছে, কিন্তু আমরা করছি না এখনো যে পদক্ষেপ এ. আমরা করছি না এ ধরণের অ্যারের ডান অর্ধেক. আমরা সাজান বামদিকের আছেন অ্যারে অর্ধেক. আর শুধু অনুরোধে জন্য এর একটু বেশি হচ্ছে পরিষ্কার, তাই আমি পাঠাতে পারেন কি পদক্ষেপ আমরা করছি, আমি সুইচ যাচ্ছি অরেঞ্জ এই সেট রঙ. এখন, আমরা এখনও যে বিষয়ে কথা বলছি মূল অ্যারের একই বাম অর্ধেক. কিন্তু আমি করতে সক্ষম দ্বারা যে আশা করছি বিভিন্ন আইটেম রং পড়ুন, এটা একটু বেশি করতে হবে এখানে কি ঘটছে পরিষ্কার. 

ঠিক আছে, তাই এখন আমরা আছে একটি তিনটি উপাদান অ্যারের. আমরা এই বাম অর্ধেক না কিভাবে এখনও এই পদক্ষেপ যা অ্যারে,? আমরা বাম বাছাই করার চেষ্টা করছেন ইটের লাল অ্যারে অর্ধেক বাম অর্ধেক যার আমি এখন কমলা রঙের থাকেন. 

ওয়েল, আমরা চেষ্টা এবং পারে আবার এই প্রক্রিয়া পুনরাবৃত্তি. তাই আমরা এখনও করছি বাছাই করার চেষ্টা মাঝখানে পূর্ণ অ্যারের বাম অর্ধেক. বাম অর্ধেক অ্যারে, আমি শুধু যাচ্ছি ইচ্ছামত সিদ্ধান্ত নিতে যে বাম অর্ধেক ডান অর্ধেক চেয়ে ছোট হতে হবে, এই ঘটবে কারণ তিনটি উপাদান দ্বারা গঠিত. 

আর তাই আমি বলতে যাচ্ছি বাম অর্ধেক অ্যারের বাম অর্ধেক শুধু উপাদান পাঁচটি নয়. পাঁচ, একটি একক উপাদান হচ্ছে অ্যারে, আমরা তা বাছাই কিভাবে জানেন. তাই পাঁচটি সাজানো হয়. আমরা শুধু যে ঘোষণা করতে যাচ্ছেন. এটি একটি একক উপাদান অ্যারে. 

সুতরাং আমরা এখন সাজানো করেছি বাম half-- বাম অর্ধেক কিংবা বলা যায়, আমরা সাজানো করেছি অরেঞ্জ বাম অর্ধেক. সুতরাং এখন, যাতে এখনও সম্পূর্ণ সার্বিক অ্যারে এর বাম অর্ধেক, আমরা ডান অর্ধেক বাছাই করতে হবে অরেঞ্জ, বা এই বিষয় নিয়ে. আমরা যে কিভাবে করব? ওয়েল, আমরা একটি দুটি উপাদান অ্যারে আছে. আমরা বাম অর্ধেক বাছাই করতে পারেন দুটি যা অ্যারের. দুই একটি একক উপাদান. তাই এটি ডিফল্টরূপে সাজানো. তারপর আমরা ডান অর্ধেক সাজাতে পারেন অ্যারে, এক যে অংশ. ডিফল্টরূপে যে সাজানোর. 

এই এখন প্রথমবার আমরা একটি একত্রীকরণ ধাপে পৌঁছে গেছেন. আমরা যদিও, সম্পন্ন আমরা এখন ধরনের down-- নেস্টেড করছি এবং যে চতুর কতকাংশে recursion সঙ্গে জিনিস, হয় আপনি আপনার রাখা প্রয়োজন আমরা যেখানে প্রায় মাথা. সুতরাং আমরা বাম সাজানোর করেছি কমলা অংশ অর্ধেক. 

এবং এখন, আমরা বাছাই মাঝখানে আছেন কমলা অংশ ডান অর্ধেক. এবং যে প্রক্রিয়ার মধ্যে, আমরা ধাপে উপর হতে এখন প্রায়, একসঙ্গে দুই আংশিক একত্রীকরণ. আমরা দুই অর্ধেক তাকান অ্যারের, আমরা দুটি এবং এক দেখতে. যা উপাদান ছোট? এক. 

তারপর যা উপাদান ছোট? ওয়েল, এটা দুই বা কিছুই না. সুতরাং এটি দুটি. তাই এখন, শুধু আবার ফ্রেমে আমরা প্রেক্ষাপটে যেখানে, আমরা সাজানো আছে অরেঞ্জ বাম অর্ধেক এবং উৎপত্তি ডান অর্ধেক. আমি রং পরিবর্তন করেছি জানি আমরা কোথায় ছিলাম আবার, কিন্তু যে. এবং কারণ আমি এই করেনি এই প্রক্রিয়া কারণ হয় নিচে iterating, বর্তা যাচ্ছে. আমরা বাম সাজানো করেছি সাবেক কমলা অর্ধেক এবং সাবেক কমলা ডান অর্ধেক. 

এখন, আমরা যারা একত্রীকরণ প্রয়োজন একসঙ্গে খুব দুই অর্ধেক. যে আমরা করছি পদক্ষেপ. তাই আমরা সব বিবেচনা এখন সবুজ হয় উপাদান, মূল অ্যারের বাম অর্ধেক. এবং আমরা যারা একত্রীকরণ একই প্রক্রিয়া ব্যবহার আমরা দুই মার্জ জন্য করেনি এবং এক মাত্র একটি মুহূর্ত আগে. 

বাম অর্ধেক, ক্ষুদ্রতম বাম অর্ধেক উপাদান পাঁচটি নয়. ক্ষুদ্রতম উপাদান ডান অর্ধেক এক. যারা যা ছোট? এক. 

ক্ষুদ্রতম উপাদান বাম অর্ধেক হয় নাই বললাম. ক্ষুদ্রতম উপাদান ডান অর্ধেক দুটি. ক্ষুদ্রতম কী? দুই. এবং তারপর সর্বশেষে পাঁচটি এবং কিছু না, আমরা পাঁচ বলতে পারেন. 

ঠিক আছে, তাই বড় ছবি, এর দিন একটি দ্বিতীয় জন্য একটি বিরতি নিয়ে আমরা যেখানে জিনিসটা. আমরা থেকে শুরু করে খুব শুরুতে আমরা এখন জন্য সম্পন্ন সার্বিক অ্যারের শুধু এখানে pseudocode কোড এক ধাপ. আমরা সাজানো আছে অ্যারের বাম অর্ধেক. 

মূল যে প্রত্যাহার যাতে পাঁচটি, দুই, এক ছিল. এই প্রক্রিয়ার মধ্য দিয়ে যাচ্ছে দ্বারা এবং নিচে পাখির বাসা এবং পুনরায়, সমস্যা বিরতি অব্যাহত নিচে ছোট এবং ছোট ভাগে, আমরা এখন সম্পন্ন pseudocode হয় এক ধাপ সমগ্র শুরু অ্যারের জন্য. আমরা তার বাম অর্ধেক সাজানো আছে. 

তাই এখন আমি কি সেখানে হিমায়িত করা যাক. এবং এখন এর ডান সাজানোর দিন মূল অ্যারে অর্ধেক. আর আমরা যে কাজ করতে যাচ্ছেন একই পুনরাবৃত্ত মাধ্যমে যাচ্ছে কিছু নিচে ভঙ্গ প্রক্রিয়া এবং তারপর তাদের একসাথে মার্জ. 

সুতরাং বাম অর্ধেক লাল, বা বাম অর্ধেক মূল ডান অর্ধেক অ্যারে, আমি বলতে যাচ্ছি তিন বছর. আবার, আমি এখানে সামঞ্জস্যপূর্ণ হওয়া করছি. আপনি একটি বিজোড় থাকে উপাদান সংখ্যা, এটা সত্যিই তা কোন ব্যাপার না আপনি বাকি এক ছোট করা বা সঠিক এক ছোট. 

কি বিষয়ে যখনই আপনি যে আবহ এই সমস্যার সম্মুখীন একটি একত্রীকরণ, আপনি সঙ্গতিপূর্ণ হতে হবে. আপনি পারেন সবসময় প্রয়োজন একটি বাম দিকে ছোট করা বা সবসময় করতে হবে ডান দিকে ছোট. এখানে, আমি সবসময় বাছাই করেছেন বাম দিকে ছোট করা যখন আমার অ্যারের, বা আমার উপ-অ্যারে, একটি বিজোড় আকারের হয়. 

তিনটি একটি একক উপাদান, এবং তাই এটি সাজানো হয়. আমরা যে ধৃষ্টতা leveraged করেছি আমাদের সমগ্র প্রক্রিয়া চলাকালে এ পর্যন্ত. তাই এখন আমি কি অধিকার সাজানোর দিন ডান অর্ধেক অর্ধেক, বা লাল ডান অর্ধেক. 

আবার, আমরা এই নিচে বিভক্ত করতে হবে. এটি একটি একক উপাদান অ্যারের নয়. আমরা এটা সাজানো ডিক্লেয়ার করতে পারেন না. আর তাই প্রথম, আমরা চলুন বাম অর্ধেক বাছাই. 

বাম অর্ধেক একটি একক উপাদান, তাই এটি ডিফল্টরূপে সাজানোর. তারপর আমরা ডান সাজানোর চলুন একটি একক উপাদান যা অর্ধেক. এটি ডিফল্টরূপে সাজানো. আর এখন, আমরা একসাথে ঐ দুটি মার্জ করতে পারবেন. চারটি ছোট হয়, এবং তারপর ছয় ছোট. 

আবার কি আমরা এই সময়ে কাজ করেছেন? আমরা বাম সাজানো করেছি ডান অর্ধেক অর্ধেক. বা আসল ফিরে যাচ্ছে সেখানে যে রং, আমরা বাম সাজানো করেছি নরম লাল অর্ধেক. এটি মূলত একটি অন্ধকার ইটের ছিল লাল এবং এখন এটি একটি নরম লাল, অথবা এটি একটি নরম লাল ছিল. 

এবং তারপর আমরা সাজানো করেছি নরম লাল ডান অর্ধেক. এখন, ভাল, তারা ঠিক, আবার সবুজ আছেন আমরা একটি প্রক্রিয়ার মধ্য দিয়ে যাচ্ছেন, কারণ. আর আমরা পুনরাবৃত্তি আছে এই বহুবার. 

তাই এখন আমরা যারা মার্জ করতে পারবেন একসাথে দুই অর্ধেক. এবং যে আমরা এখানে কি কি. কালো রেখা তাই শুধু বাম অর্ধেক ভাগ এবং এই সাজানোর অংশ ডান অর্ধেক. 

আমরা ক্ষুদ্রতম মান তুলনা অ্যারে বামদিকে অথবা আমাকে মাফ, ক্ষুদ্রতম বাম অর্ধেক মূল্য ডান ক্ষুদ্রতম মান অর্ধেক এবং তিনটি ছোট যে এটি. এবং এখন একটি অপ্টিমাইজেশান একটি বিট, ডান? কিছুই আসলে আছে বাম পাশে বাম. 

অবশিষ্ট কিছুই নেই বাম দিকে, তাই আমরা দক্ষতার পারেন শুধু আমরা ঘোষণা করতে পারেন move-- এটা বাকি আসলে সাজানো এবং শুধু এটি ট্যাক কিছুই নেই, কারণ, প্রথম বিরুদ্ধে তুলনা অন্য. আর আমরা জানি ডান দিকে যে ডাইন সাজানো হয়. 

ঠিক আছে, তাই এখন এর আবার নিথর দেওয়া এবং আমরা গল্পের চিন্তা করা যেখানে. সার্বিক অ্যারের মধ্যে, আমরা কি সম্পন্ন করেছেন? আমরা আসলে সাধন করেছি এখন এক এবং ধাপে দুই ধাপ. আমরা বাম অর্ধেক সাজানো, এবং আমরা ডান অর্ধেক সাজানো. 

সুতরাং এখন, যে অবশেষ সব আমাদের জন্য নয় একসাথে ঐ দুটি আংশিক একত্রীকরণ করতে. সুতরাং আমরা সর্বনিম্ন মূল্যবান তুলনা অ্যারের প্রতিটি অর্ধেক উপাদান এবং ঘুরে এগিয়ে যান. এক থেকে তিন কম হয়, তাই এক যায়. 

দুই তিন কম হয়, তাই দুই যায়. তিনটি 5 কম হয়, তাই তিন যায়. চার 5 কম হয়, তাই চার যায়. তারপর পাঁচ, ছয় কম হয় এবং ছয় সব যে অবশেষ হয়. 

এখন, আমি জানি, যে পদক্ষেপ অনেকটা ছিল. আর আমরা অনেক বাকি থাকেন আমাদের WAKE মেমরি. আর ঐ যে ধূসর স্কোয়ার আছে কি. যে একটি গ্রহণ মত এবং এটি সম্ভবত অনুভূত সন্নিবেশ সাজানোর চেয়ে আর অনেক, বাবল সাজান, অথবা নির্বাচন সাজানোর. 

কিন্তু আসলে, কারণ একটি এই প্রক্রিয়ার অনেক একই সময়ের মধ্যে এ ঘটছে যা, আবার, আমরা করব কিছু আমরা যে বিষয়ে কথা যখন আমার সাথে কথা বলতে ভবিষ্যতে মধ্যে recursion video-- আসলে এই অ্যালগরিদম পরিষ্কারভাবে মৌলিকভাবে যে কোন কিছুর চেয়ে আলাদা আমরা আগে দেখা যায় কিন্তু উল্লেখযোগ্যভাবে হয় আরো দক্ষ. 

কেন হল? ভাল, খুব খারাপ এ কেস দৃশ্যকল্প, আমরা আছে n উপাদান আপ বিভক্ত এবং তারপর তাদের পুনর্মিলিত. কিন্তু আমরা পুনর্মিলিত যখন তাদের, আমরা কি করছেন মূলত দ্বিত্ব হয় ছোট অ্যারে মাপ. আমরা এক উপাদান একটি গুচ্ছ আছে অ্যারে যে আমরা কার্যকরভাবে দুটি উপাদান অ্যারে মধ্যে একত্রিত করা. এবং তারপর আমরা যারা নিতে দুটি উপাদান অ্যারে এবং সেগুলি একসঙ্গে মেশা তাই চার উপাদান অ্যারে, এবং, এবং তাই, এবং তাই, আমরা যতক্ষণ একটি একক এন উপাদান অ্যারে আছে. 

কিন্তু কতগুলি doublings এটি এন পেতে সময় লাগবে? ফিরে ফোন বই উদাহরণ চিন্তা করুন. কত বার আমরা বিছিন্ন করা আছে অর্ধেক ফোন বই, কতগুলি আরো বার আমরা ফোনে বই বিছিন্ন করা আছে অর্ধেক, যদি টেলিফোন বইয়ের আকার দ্বিগুণ? শুধু এক ডান, আছে? 

তাই কিছু বাছাই আছে এখানে লগারিদমিক উপাদান. কিন্তু আমরা এখনও আছে অন্তত এন উপাদানের সব তাকান. , লক দৃশ্যকল্প তাই সাজানোর n log n রান একত্রীকরণ. আমরা তাকান আছে এন উপাদানের সব, এবং আমরা তাদের একত্রিত করতে হবে একসঙ্গে লগ n ধাপ কেতা. শ্রেষ্ঠ কেস দৃশ্যকল্প ইন, অ্যারে পুরোপুরি সাজানো হয়. দারুণ. কিন্তু আলগোরিদিম উপর ভিত্তি করে আমরা এখানে আছে আমরা এখনও বিভক্ত এবং পুনর্মিলিত আছে. এই ক্ষেত্রে যদিও, পুনর্সমম্বয় অকার্যকর ধরনের. এটি প্রয়োজন না হয়. কিন্তু আমরা এখনও মাধ্যমে যেতে যাহাই হউক না কেন, পুরো প্রক্রিয়া. 

তাই সবচেয়ে ভাল ক্ষেত্রে এবং সবচেয়ে খারাপ ক্ষেত্রে, এই অ্যালগরিদম এন লগ n সময়ে সঞ্চালিত হয়. সাজান মার্জ স্পষ্টভাবে একটি বিট trickier হয় অন্যান্য প্রধান বাছাই আলগোরিদিম চেয়ে আমরা CS50 সম্পর্কে বললাম কিন্তু করেছি অনেক বেশি শক্তিশালী. 

আর যদি তাই আপনি কি এটি অনুষ্ঠানে এটি প্রয়োজন বা সাজাতে এটি ব্যবহার করার জন্য বড় তথ্য সংকলন, পেয়ে recursion ধারণা কাছাকাছি আপনার মাথা সত্যিই শক্তিশালী হতে যাচ্ছে. আর এটা করতে যাচ্ছে আপনার প্রোগ্রাম সত্যিই অনেক বেশি দক্ষ অন্য কিছু বনাম সাজান একত্রীকরণ ব্যবহার. আমি ডগ লয়েড আছি. এটি CS50.