পাইথনে মার্জ সর্ট ব্যাখ্যা কর

মার্জ সর্ট একটি সাজানোর কৌশল। এটি একটি দক্ষ বাছাই অ্যালগরিদম যার একটি সময় জটিলতা (n logn ) যেখানে n হল বিন্যাসের দৈর্ঘ্য।

মার্জ সর্ট হল একটি অ্যালগরিদম যা ডিভাইড অ্যান্ড কনকার্স প্যারাডাইম অনুসরণ করে। এটি ক্রমাগত অ্যারেটিকে দুটি সমান ভাগে ভাগ করে। পরে এটি প্রতিটি একটি একক উপাদান সহ তালিকাগুলিকে সাজানো শুরু করে এবং ক্রমাগতভাবে সাজানো তালিকাগুলিকে একত্রিত করে সম্পূর্ণ সাজানো তালিকা তৈরি করে৷

তাই, আমরা একটি সাজানো অ্যারে পাই।

উদাহরণ

বেগুনি বাক্স এবং কালো তীরগুলি তালিকাটিকে দুটি ভাগে বিভক্ত দেখায়৷

সবুজ বাক্স এবং লাল তীর দুটি সাজানো তালিকার একত্রীকরণ দেখায়৷

একত্রীকরণ সাজানোর প্রয়োগ করুন

তালিকাটিকে দুটি অর্ধে বিভক্ত করা বেশ সহজ এবং এটি পুনরাবৃত্তভাবে করা হয় যতক্ষণ না আমাদের কেবল একটি উপাদান অবশিষ্ট থাকে। পরে মার্জিং পদ্ধতিটি সম্পন্ন হয় যা আসলে আমরা দুটি সাজানো তালিকাকে একত্রিত করার যুক্তি প্রয়োগ করি৷

উদাহরণ

মার্জ ফাংশন দুটি সাজানো অ্যারেকে একত্রিত করতে নেয়। A1 এর সবচেয়ে সামনের উপাদানটিকে a2 এর সবচেয়ে সামনের উপাদানের সাথে তুলনা করা হয়। দুটির মধ্যে সবচেয়ে ছোটটি তালিকা সি-তে যোগ করা হয় এবং সেই অ্যারের পয়েন্টারটি বৃদ্ধি পায়।

def merge(a1,a2):
   c=[]
   x=0
   y=0
   while(x<len(a1) and y<len(a2)):
      if(a1[x]<a2[y]):
         c.append(a1[x])
         x+=1
      else:
         c.append(a2[y])
         y+=1
   while(x<len(a1)):
      c.append(a1[x])
      x+=1
   while(y<len(a2)):
      c.append(a2[y])
      y+=1
   return c

def mergesort(array):
   if(len(array)==1):
      return array
   mid=(len(array))//2
   a1=mergesort(array[:mid])
   a2=mergesort(array[mid:])
   return merge(a1,a2)
array=[2,3,1,5,4,6,8,10,7,9]
print(mergesort(array))

আউটপুট

[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]