पायथन में मर्ज सॉर्ट की व्याख्या करें

मर्ज सॉर्ट एक सॉर्टिंग तकनीक है। यह एक कुशल छँटाई एल्गोरिथ्म है जिसकी समय जटिलता (n logn .) है ) जहां n क्रमबद्ध करने के लिए सरणी की लंबाई है।

मर्ज सॉर्ट एक एल्गोरिथम है जो डिवाइड एंड कॉनक्वेर्स प्रतिमान का अनुसरण करता है। यह सरणी को लगातार दो बराबर हिस्सों में विभाजित करता है। बाद में यह प्रत्येक एक तत्व वाली सूचियों को छांटना शुरू कर देता है और पूरी क्रमबद्ध सूची बनाने के लिए क्रमबद्ध सूचियों को लगातार मर्ज करता है।

इसलिए, हम एक क्रमबद्ध सरणी प्राप्त करते हैं।

उदाहरण

बैंगनी बॉक्स और काले तीर सूची को दो हिस्सों में विभाजित करते हुए दिखाते हैं।

हरे बक्से और लाल तीर दो क्रमबद्ध सूचियों के विलय को दिखाते हैं।

मर्ज सॉर्ट लागू करें

सूची को दो हिस्सों में विभाजित करना काफी आसान है और इसे पुनरावर्ती रूप से तब तक किया जाता है जब तक हमारे पास केवल एक तत्व शेष न हो। बाद में विलय की प्रक्रिया की जाती है जो वास्तव में है जहां हम दो क्रमबद्ध सूचियों को एक साथ मिलाने के तर्क को लागू करते हैं।

उदाहरण

मर्ज फ़ंक्शन दो सॉर्ट किए गए सरणियों को मर्ज करने के लिए लेता है। a1 के सबसे सामने वाले तत्व की तुलना a2 के सबसे सामने वाले तत्व से की जाती है। सूची c में दो में से सबसे छोटा जोड़ दिया जाता है और उस सरणी के सूचक को बढ़ा दिया जाता है।

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]