पायथन में मर्ज सॉर्ट समझाया गया

मर्ज सॉर्ट एक सॉर्टिंग तकनीक है। यह एक कुशल सॉर्टिंग एल्गोरिथम है जिसकी टाइम कॉम्प्लेक्सिटी O(n log n) होती है जहां 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]