मर्ज सॉर्ट

Python में Data Structures और Algorithms

Miriam Antona

Software engineer

मर्ज सॉर्ट

Divide and conquer का पालन करता है
- Divide
  - समस्या को छोटे सब-प्रॉब्लम्स में बाँटता है
- Conquer
  - सब-प्रॉब्लम्स को रिकर्सिव तरीक़े से सॉल्व करता है
- Combine
  - सब-प्रॉब्लम्स के सॉल्यूशन्स को जोड़कर फ़ाइनल सॉल्यूशन मिलता है

मर्ज सॉर्ट - क्रिया में

अनियमित संख्याओं वाली सूची का आरेखात्मक चित्रण.

मर्ज सॉर्ट - क्रिया में

अनियमित संख्याओं वाली सूची का आरेखात्मक चित्रण. सूची को दो भागों में बाँटा गया है.

मर्ज सॉर्ट - क्रिया में

अनियमित संख्याओं वाली सूची का आरेखात्मक चित्रण. सूची दो भागों में बँटी है. दो नई सूचियाँ बनी हैं: पहली में मूल सूची का बायाँ आधा, दूसरी में दायाँ आधा.

मर्ज सॉर्ट - क्रिया में

अनियमित संख्याओं वाली सूची का आरेखात्मक चित्रण. नई सूचियाँ दो भागों में बाँटी गई हैं.

मर्ज सॉर्ट - क्रिया में

अनियमित संख्याओं वाली सूची का आरेखात्मक चित्रण. पिछली विभाजित सूचियों से नई उप-सूचियाँ बनी हैं.

मर्ज सॉर्ट - क्रिया में

มर्ज सॉर्ट - क्रिया में

मर्ज सॉर्ट - क्रिया में

अनियमित संख्याओं वाली सूची का आरेखात्मक चित्रण. अंतिम विभाजित सूचियों के एलिमेंट्स को सॉर्ट किया गया है.

मर्ज सॉर्ट - क्रिया में

अनियमित संख्याओं वाली सूची का आरेखात्मक चित्रण. अंतिम विभाजित सूचियों के एलिमेंट्स को मर्ज कर क्रम में रखा गया है.

मर्ज सॉर्ट - क्रिया में

अनियमित संख्याओं वाली सूची का आरेखात्मक चित्रण. अंतिम विभाजित सूचियों के एलिमेंट्स को मर्ज कर क्रम में रखा गया है. सभी एलिमेंट्स सॉर्ट हो गए हैं.

मर्ज सॉर्ट - इम्प्लीमेंटेशन

def merge_sort(my_list):
  if len(my_list) > 1:

    mid = len(my_list)//2
    left_half = my_list[:mid]
    right_half = my_list[mid:]

    merge_sort(left_half)
    merge_sort(right_half)


    i = j = k = 0

    while i < len(left_half) and j < len(right_half):

      if left_half[i] < right_half[j]:

        my_list[k] = left_half[i]

        i += 1

      else:

        my_list[k] = right_half[j]

        j += 1

      k += 1

    while i < len(left_half):

      my_list[k] = left_half[i]
      i += 1
      k += 1


    while j < len(right_half):
      my_list[k] = right_half[j]
      j += 1
      k += 1

my_list = [35,22,90,4,50,20,30,40,1]
merge_sort(my_list)
print(my_list)

[1, 4, 20, 22, 30, 35, 40, 50, 90]

मर्ज सॉर्ट - कॉम्प्लेक्सिटी

Worst case: $O(n\log{}n)$
- बबल सॉर्ट, सेलेक्शन सॉर्ट, और इंसर्शन सॉर्ट से काफ़ी बेहतर
- बड़ी सूचियाँ सॉर्ट करने के लिए उपयुक्त
Average case: $\Theta(n\log{}n)$
Best case: $\Omega(n\log{}n)$
- अन्य एल्गोरिदम (जैसे bubble sort, insertion sort) का बेस्ट केस बेहतर होता है
Space complexity: $O(n)$
- उन एल्गोरिदम से बदतर स्पेस, जिनका $O(1)$ है
कुछ वेरिएंट्स इस स्पेस लागत को घटाते हैं

अभ्यास करते हैं!

Python में Data Structures और Algorithms