Table of Contents
मर्ज सॉर्ट एक लोकप्रिय तुलना-आधारित सॉर्टिंग एल्गोरिदम है जो इसकी दक्षता और पूर्वानुमान प्रदर्शन के लिए जाना जाता है। यह समझने के लिए कि यह किस तरह से तुलना करता है, इसकी क्रियान्वयन को अनुकूलित करने और विभिन्न परिदृश्यों में इसके प्रदर्शन का विश्लेषण करने में मदद कर सकता है।
मर्ज सॉर्ट की मूल अवधारणा
मर्ज सॉर्ट एक सारणी को छोटे उपरे में विभाजित करता है, प्रत्येक उपरे को सॉर्ट करता है, और फिर उन्हें एक साथ वापस ला देता है। कोर ऑपरेशन में मर्ज प्रक्रिया के दौरान तत्वों की तुलना शामिल है, जो किए गए तुलना की कुल संख्या निर्धारित करता है।
विलय के दौरान तुलना की गणना
विलय चरण के दौरान, तुलना तब होती है जब दो छंटनी वाले उपरे से छोटे तत्व का चयन किया जाता है। प्रत्येक जोड़े की तुलना में तत्वों की तुलना में, एक तुलना की गणना की जाती है। यदि उपरे में आकार n1 ] और n2 ], तो अधिकतम संख्या उनमें विलय करने की आवश्यकता है n1 + n2 - 1 ]].
कुल तुलना का आकलन
विलय में तुलना की कुल संख्या को प्रत्येक विलय ऑपरेशन का विश्लेषण करके आवर्ती के सभी स्तरों पर किया जा सकता है। आकार की एक सारणी के लिए n], कुल तुलना मोटे तौर पर हैं:
- n log2 n ] औसत और सबसे खराब मामले में।
- प्रत्येक स्तर के पुनरावृत्ति में सबरे को विलय करना शामिल है, जिसमें कुल तुलना सभी स्तरों पर योग करती है।
- प्रति स्तर की तुलना की संख्या दोगुनी होती है क्योंकि उपरे बड़े हो जाते हैं।
प्रैक्टिकल गणना विधि
तुलनात्मक गणना करने के लिए, विलय प्रक्रिया को अनुकरण करें या पुनरावर्ती संबंध का उपयोग करें:
C(n) = C(N)]+ C(N)+(N -1)]]
जहाँ C(n) आकार की एक सरणी के लिए कुल तुलना है n]. यह पुन:प्राप्त सूत्र subarrays में तुलना और विलय के दौरान खातों के लिए खाता है।