Merge sort হল একটি divide-and-conquer, স্থিতিশীল সর্ট যা গ্যারান্টিযুক্ত O(n log n) সময়ে চলে। এটি অ্যারেকে অর্ধেক ভাগ করে, প্রতিটি অর্ধ পুনরাবৃত্তভাবে সর্ট করে, তারপর দুটি সর্টকৃত অর্ধ মার্জ করে।
ধারণা
একটি একক উপাদান ইতিমধ্যে সর্ট করা হয়েছে (বেস কেস)। দুটি সর্টকৃত তালিকা মার্জ করা রৈখিক, এবং আমরা log n স্তরের মার্জিং করি।
