एल्गोरिदम मर्ज करें

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

आवेदन

मर्ज सॉर्ट के लिए एक उदाहरण

मर्ज एल्गोरिथ्म मर्ज सॉर्ट एल्गोरिदम में एक महत्वपूर्ण भूमिका निभाता है, एक तुलनात्मक सॉर्ट | तुलना-आधारित सॉर्टिंग एल्गोरिदम। वैचारिक रूप से, मर्ज सॉर्ट एल्गोरिथ्म में दो चरण होते हैं:

रिकर्सन (कंप्यूटर विज्ञान) सूची को (लगभग) समान लंबाई की उप-सूचियों में विभाजित करता है, जब तक कि प्रत्येक उप-सूची में केवल एक तत्व न हो, या पुनरावृत्त (नीचे से ऊपर) मर्ज सॉर्ट के मामले में, n तत्वों की सूची को आकार 1 की n उप-सूचियों के रूप में मानें। एक एकल तत्व वाली सूची, परिभाषा के अनुसार, क्रमबद्ध होती है।
एक नई क्रमबद्ध उपसूची बनाने के लिए उपसूचियों को बार-बार मर्ज करें जब तक कि एकल सूची में सभी तत्व शामिल न हो जाएं। एकल सूची क्रमबद्ध सूची है.

मर्ज सॉर्ट एल्गोरिदम में मर्ज एल्गोरिदम का बार-बार उपयोग किया जाता है।

चित्रण में मर्ज सॉर्ट का एक उदाहरण दिया गया है। यह 7 पूर्णांकों की एक अवर्गीकृत सारणी से प्रारंभ होता है। सरणी को 7 विभाजनों में विभाजित किया गया है; प्रत्येक विभाजन में 1 तत्व होता है और उसे क्रमबद्ध किया जाता है। क्रमबद्ध विभाजनों को फिर बड़े, क्रमबद्ध, विभाजन बनाने के लिए विलय कर दिया जाता है, जब तक कि 1 विभाजन, क्रमबद्ध सरणी, शेष न रह जाए।

दो सूचियों का विलय

दो क्रमबद्ध सूचियों को एक में विलय करना रैखिक समय और रैखिक या स्थिर स्थान (डेटा एक्सेस मॉडल के आधार पर) में किया जा सकता है। निम्नलिखित छद्मकोड एक एल्गोरिदम प्रदर्शित करता है जो इनपुट सूचियों (या तो लिंक की गई सूचियाँ या ऐरे डेटा संरचना) को मर्ज करता है $A$ और $B$ एक नई सूची में $C$ .^[1]^[2]^: 104 कार्यक्रम head किसी सूची का पहला तत्व उत्पन्न करता है; किसी तत्व को हटाने का अर्थ है उसे उसकी सूची से हटाना, आमतौर पर एक पॉइंटर या इंडेक्स को बढ़ाकर।

एल्गोरिदम मर्ज (ए, बी) है
    इनपुट ए, बी: सूची
    रिटर्न सूची

    सी := नई खाली सूची
    जबकि A खाली नहीं है और B खाली नहीं है
        यदि सिर(ए) ≤ सिर(बी) तो
            शीर्ष (ए) को सी में जोड़ें
            ए का सिर गिरा दो
        अन्य
            शीर्ष (बी) को सी से जोड़ें
            बी का सिर गिरा दो

    // अब तक, या तो ए या बी खाली है। अन्य इनपुट सूची को खाली करना बाकी है।
    जबकि A खाली नहीं है
        शीर्ष (ए) को सी में जोड़ें
        ए का सिर गिरा दो
    जबकि B खाली नहीं है
        शीर्ष (बी) को सी से जोड़ें
        बी का सिर गिरा दो

    वापसी सी

जब इनपुट लिंक्ड सूचियाँ होते हैं, तो इस एल्गोरिदम को केवल स्थिर मात्रा में कार्य स्थान का उपयोग करने के लिए कार्यान्वित किया जा सकता है; सूचियों के नोड्स में पॉइंटर्स का बहीखाता पद्धति और अंतिम मर्ज की गई सूची के निर्माण के लिए पुन: उपयोग किया जा सकता है।

मर्ज सॉर्ट एल्गोरिदम में, इस सबरूटीन का उपयोग आम तौर पर दो उप-सरणी को मर्ज करने के लिए किया जाता है A[lo..mid], A[mid+1..hi] एकल सारणी का A. यह उप-सरणियों को एक अस्थायी सरणी में कॉपी करके, फिर ऊपर मर्ज एल्गोरिथ्म को लागू करके किया जा सकता है।^[1] एक अस्थायी सरणी के आवंटन से बचा जा सकता है, लेकिन गति और प्रोग्रामिंग आसानी की कीमत पर। विभिन्न इन-प्लेस मर्ज एल्गोरिदम तैयार किए गए हैं,^[3] कभी-कभी उत्पादन के लिए रैखिक-समय सीमा का त्याग करना पड़ता है $O (n log n)$ कलन विधि;^[4] देखना Merge sort § Variants चर्चा के लिए।

K-वे विलय

$k$ -वे विलय बाइनरी विलय को एक मनमाना संख्या में सामान्यीकृत करता है $k$ क्रमबद्ध इनपुट सूचियों का। के अनुप्रयोग $k$ -वे मर्जिंग विभिन्न सॉर्टिंग एल्गोरिदम में उत्पन्न होती है, जिसमें धैर्य सॉर्टिंग भी शामिल है^[5] और एक बाहरी सॉर्टिंग एल्गोरिदम जो इसके इनपुट को विभाजित करता है $k = .mw-parser-output .sfrac{white-space:nowrap}.mw-parser-output .sfrac.tion,.mw-parser-output .sfrac .tion{display:inline-block;vertical-align:-0.5em;font-size:85%;text-align:center}.mw-parser-output .sfrac .num,.mw-parser-output .sfrac .den{display:block;line-height:1em;margin:0 0.1em}.mw-parser-output .sfrac .den{border-top:1px solid}.mw-parser-output .sr-only{border:0;clip:rect(0,0,0,0);height:1px;margin:-1px;overflow:hidden;padding:0;position:absolute;width:1px}1/M − 1$ जो ब्लॉक मेमोरी में फिट होते हैं, उन्हें एक-एक करके क्रमबद्ध करता है, फिर इन ब्लॉकों को मर्ज करता है।^[2]^{: 119–120}

इस समस्या के कई समाधान मौजूद हैं। एक सरल उपाय यह है कि इसके ऊपर एक लूप बनाया जाए $k$ हर बार न्यूनतम तत्व चुनने के लिए सूचियाँ, और इस लूप को तब तक दोहराएँ जब तक कि सभी सूचियाँ खाली न हो जाएँ:

इनपुट: की एक सूची $k$ सूचियाँ।
जबकि कोई भी सूची गैर-रिक्त है:
- न्यूनतम प्रथम तत्व वाले को खोजने के लिए सूचियों पर लूप करें।
- न्यूनतम तत्व को आउटपुट करें और इसे इसकी सूची से हटा दें।

सबसे अच्छा, सबसे खराब और औसत मामला, यह एल्गोरिदम प्रदर्शन करता है $(k -1)(n - k / 2)$ तत्व की तुलना यदि कुल हो तो अपना कार्य करें $n$ सूचियों में तत्व।^[6] सूचियों को उनके पहले तत्व द्वारा कुंजीबद्ध प्राथमिकता कतार (हीप (डेटा संरचना)|मिन-हीप) में संग्रहीत करके इसे बेहतर बनाया जा सकता है:

एक मिन-ढेर बनाएँ $h$ की $k$ सूचियाँ, पहले तत्व को कुंजी के रूप में उपयोग करती हैं।
जबकि कोई भी सूची गैर-रिक्त है:
- होने देना $i = find-min(h)$ .
- सूची का पहला तत्व आउटपुट करें $i$ और इसे इसकी सूची से हटा दें।
- पुनः ढेर लगाना $h$ .

आउटपुट (फाइंड-मिन) के लिए अगले सबसे छोटे तत्व की खोज करना और ढेर क्रम को पुनर्स्थापित करना अब किया जा सकता है $O (log k)$ समय (अधिक विशेष रूप से, $2⌊log k ⌋$ तुलना^[6]), और पूरी समस्या का समाधान किया जा सकता है $O (n log k)$ समय (लगभग $2 n ⌊log k ⌋$ तुलना)।^[6]^[2]^{: 119–120}

समस्या के लिए तीसरा एल्गोरिदम फूट डालो और जीतो एल्गोरिदम समाधान है जो बाइनरी मर्ज एल्गोरिदम पर आधारित है:

अगर $k = 1$ , एकल इनपुट सूची को आउटपुट करें।
अगर $k = 2$ , एक बाइनरी मर्ज निष्पादित करें।
अन्यथा, पहले को पुनरावर्ती रूप से मर्ज करें $⌊ k /2⌋$ सूचियाँ और अंतिम $⌈ k /2⌉$ सूचियाँ, फिर इन्हें बाइनरी मर्ज करें।

जब इस एल्गोरिथम में इनपुट सूचियों को लंबाई के आधार पर क्रमबद्ध किया जाता है, सबसे पहले सबसे छोटी, तो इससे कम की आवश्यकता होती है $n ⌈log k ⌉$ तुलना, यानी, ढेर-आधारित एल्गोरिदम द्वारा उपयोग की जाने वाली संख्या के आधे से भी कम; व्यवहार में, यह हीप-आधारित एल्गोरिथम जितना तेज़ या धीमा हो सकता है।^[6]

समानांतर विलय

बाइनरी मर्ज एल्गोरिदम का एक कार्य समानता संस्करण मर्ज सॉर्ट#समानांतर मर्ज सॉर्ट के बिल्डिंग ब्लॉक के रूप में काम कर सकता है। निम्नलिखित स्यूडोकोड इस एल्गोरिदम को फोर्क-जॉइन मॉडल|समानांतर विभाजन और जीत शैली (कॉर्मेन एट अल से अनुकूलित) में प्रदर्शित करता है।^[7]^: 800). यह दो क्रमबद्ध सरणियों पर काम करता है $A$ और $B$ और क्रमबद्ध आउटपुट को सरणी में लिखता है $C$ . संकेतन A[i...j] के भाग को दर्शाता है $A$ सूचकांक से $i$ द्वारा $j$ , अनन्य।

एल्गोरिदम मर्ज(ए[आई...जे], बी[के...ℓ], सी[पी...क्यू]) है
    इनपुट ए, बी, सी: सरणी
           i, j, k, ℓ, p, q : सूचकांक

    मान लीजिए m = j - i,
        एन = ℓ - के

    यदि m < n तो
        A और B को स्वैप करें // सुनिश्चित करें कि A बड़ा ऐरे है: i, j अभी भी A से संबंधित हैं; k, ℓ से B
        एम और एन स्वैप करें

    यदि m ≤ 0 तो
        वापसी // बेस केस, मर्ज करने के लिए कुछ भी नहीं

    मान लीजिए r = ⌊(i + j)/2⌋
    मान लीजिए s = बाइनरी-सर्च(A[r], B[k...ℓ])
    मान लीजिए t = p + (r - i) + (s - k)
    सी[टी] = ए[आर]

    समानांतर में करें
        मर्ज(ए[आई...आर], बी[के...एस], सी[पी...टी])
        मर्ज(ए[आर+1...जे], बी[एस...ℓ], सी[टी+1...क्यू])

एल्गोरिथ्म या तो विभाजन द्वारा संचालित होता है $A$ या $B$ , जो भी बड़ा हो, (लगभग) बराबर हिस्सों में। इसके बाद यह दूसरे एरे को पहले के मध्यबिंदु से छोटे मान वाले भाग में और बड़े या समान मान वाले भाग में विभाजित करता है। (द्विआधारी खोज सबरूटीन इंडेक्स लौटाता है $B$ कहाँ $A [r]$ होगा, अगर यह अंदर होता $B$ ; कि यह हमेशा बीच की एक संख्या है $k$ और $ℓ$ .) अंत में, हिस्सों की प्रत्येक जोड़ी को फूट डालो और जीतो एल्गोरिथ्म में मिला दिया जाता है, और चूंकि पुनरावर्ती कॉल एक दूसरे से स्वतंत्र होते हैं, इसलिए उन्हें समानांतर में किया जा सकता है। हाइब्रिड दृष्टिकोण, जहां रिकर्सन बेस केस के लिए सीरियल एल्गोरिदम का उपयोग किया जाता है, अभ्यास में अच्छा प्रदर्शन करता हुआ दिखाया गया है ^[8] समानांतर एल्गोरिदम का विश्लेषण#कुल मिलाकर दो सरणियों के लिए एल्गोरिदम द्वारा किया गया अवलोकन $n$ तत्व, यानी, इसके धारावाहिक संस्करण का चलने का समय है $O (n)$ . यह तब से इष्टतम है $n$ तत्वों को कॉपी करने की आवश्यकता है $C$ . समानांतर एल्गोरिदम के विश्लेषण की गणना करने के लिए#एल्गोरिदम का अवलोकन, एक पुनरावृत्ति संबंध प्राप्त करना आवश्यक है। चूंकि मर्ज की दो पुनरावर्ती कॉल समानांतर हैं, इसलिए केवल दो कॉलों में से महंगी पर विचार करने की आवश्यकता है। सबसे खराब स्थिति में, पुनरावर्ती कॉल में से किसी एक में तत्वों की अधिकतम संख्या अधिकतम होती है ${\textstyle {\frac {3}{4}}n}$ चूंकि अधिक तत्वों वाली सरणी पूरी तरह से आधे में विभाजित है। जोड़ रहा हूँ $\Theta \left(\log(n)\right)$ बाइनरी खोज की लागत, हम इस पुनरावृत्ति को ऊपरी सीमा के रूप में प्राप्त करते हैं:

$T_{\infty }^{\text{merge}}(n)=T_{\infty }^{\text{merge}}\left({\frac {3}{4}}n\right)+\Theta \left(\log(n)\right)$ समाधान है $T_{\infty }^{\text{merge}}(n)=\Theta \left(\log(n)^{2}\right)$ , जिसका अर्थ है कि असीमित संख्या में प्रोसेसर वाली एक आदर्श मशीन पर इतना समय लगता है।^[7]^{: 801–802}

नोट: रूटीन सॉर्टिंग एल्गोरिदम नहीं है#स्थिरता: यदि समान वस्तुओं को विभाजित करके अलग किया जाता है $A$ और $B$ , वे आपस में जुड़ जाएंगे $C$ ; अदला-बदली भी $A$ और $B$ यदि दोनों इनपुट सरणियों के बीच समान आइटम फैले हुए हैं, तो ऑर्डर नष्ट हो जाएगा। परिणामस्वरूप, जब सॉर्टिंग के लिए उपयोग किया जाता है, तो यह एल्गोरिदम एक ऐसा सॉर्ट उत्पन्न करता है जो स्थिर नहीं होता है।

दो सूचियों का समानांतर विलय

ऐसे एल्गोरिदम भी हैं जो दो क्रमबद्ध सूचियों के विलय के एक ही उदाहरण में समानता का परिचय देते हैं। इनका उपयोग फील्ड-प्रोग्रामेबल गेट एरेज़ (एफपीजीए), विशेष सॉर्टिंग सर्किट, साथ ही सिंगल-इंस्ट्रक्शन मल्टीपल-डेटा (एसआईएमडी) निर्देशों वाले आधुनिक प्रोसेसर में किया जा सकता है।

मौजूदा समानांतर एल्गोरिदम बिटोनिक सॉर्टर या सम-विषम मर्ज सॉर्ट के मर्ज भाग के संशोधनों पर आधारित हैं।^[9] 2018 में, सैतोह एम. एट अल। एमएमएस पेश किया ^[10] एफपीजीए के लिए, जो एक बहु-चक्र फीडबैक डेटापथ को हटाने पर केंद्रित था जो हार्डवेयर में कुशल पाइपलाइनिंग को रोकता था। इसके अलावा 2018 में, पापाफिलिप्पौ पी. एट अल। FLiMS की शुरुआत की ^[9]जिसने केवल आवश्यकता के द्वारा हार्डवेयर उपयोग और प्रदर्शन में सुधार किया $\log _{2}(P)+1$ के पाइपलाइन चरण $P/2$ समानता के साथ विलय करने के लिए इकाइयों की तुलना और अदला-बदली करें $P$ तत्व प्रति FPGA चक्र।

भाषा समर्थन

कुछ कंप्यूटर भाषाएँ क्रमबद्ध संग्रह (सार डेटा प्रकार) को मर्ज करने के लिए अंतर्निहित या लाइब्रेरी समर्थन प्रदान करती हैं।

सी++

C++ की मानक टेम्पलेट लाइब्रेरी में फ़ंक्शन है std::merge, जो पुनरावर्तकों की दो क्रमबद्ध श्रेणियों को मर्ज करता है, और std::inplace_merge, जो दो क्रमागत क्रमबद्ध श्रेणियों को एक ही स्थान पर विलीन कर देता है। इसके साथ में std::list (लिंक्ड सूची) वर्ग का अपना है merge विधि जो दूसरी सूची को अपने में विलीन कर देती है। मर्ज किए गए तत्वों के प्रकार को कम-से-कम का समर्थन करना चाहिए (<) ऑपरेटर, या इसे एक कस्टम तुलनित्र प्रदान किया जाना चाहिए।

C++17 अलग-अलग निष्पादन नीतियों की अनुमति देता है, अर्थात् अनुक्रमिक, समानांतर और समानांतर-अअनुक्रमित।^[11]

पायथन

पायथन (प्रोग्रामिंग भाषा) की मानक लाइब्रेरी (2.6 से) में भी एक है merge फ़ंक्शन में heapq मॉड्यूल, जो एकाधिक क्रमबद्ध पुनरावर्तनीय लेता है, और उन्हें एक एकल पुनरावृत्त में विलय कर देता है।^[12]

यह भी देखें

संदर्भ

↑ ^1.0 ^1.1 Skiena, Steven (2010). एल्गोरिथम डिज़ाइन मैनुअल (2nd ed.). Springer Science+Business Media. p. 123. ISBN 978-1-849-96720-4.
↑ ^2.0 ^2.1 ^2.2 Kurt Mehlhorn; Peter Sanders (2008). Algorithms and Data Structures: The Basic Toolbox. Springer. ISBN 978-3-540-77978-0.
↑ Katajainen, Jyrki; Pasanen, Tomi; Teuhola, Jukka (1996). "प्रैक्टिकल इन-प्लेस मर्जसॉर्ट". Nordic J. Computing. 3 (1): 27–40. CiteSeerX 10.1.1.22.8523.
↑ Kim, Pok-Son; Kutzner, Arne (2004). सममित तुलनाओं द्वारा स्थिर न्यूनतम संग्रहण विलय. European Symp. Algorithms. Lecture Notes in Computer Science. Vol. 3221. pp. 714–723. CiteSeerX 10.1.1.102.4612. doi:10.1007/978-3-540-30140-0_63. ISBN 978-3-540-23025-0.
↑ Chandramouli, Badrish; Goldstein, Jonathan (2014). Patience is a Virtue: Revisiting Merge and Sort on Modern Processors. SIGMOD/PODS.
↑ ^6.0 ^6.1 ^6.2 ^6.3 Greene, William A. (1993). के-वे मर्जिंग और के-एरी सॉर्ट्स (PDF). Proc. 31-st Annual ACM Southeast Conf. pp. 127–135.
↑ ^7.0 ^7.1 Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2009) [1990]. Introduction to Algorithms (3rd ed.). MIT Press and McGraw-Hill. ISBN 0-262-03384-4.
↑ Victor J. Duvanenko (2011), "Parallel Merge", Dr. Dobb's Journal
↑ ^9.0 ^9.1 Papaphilippou, Philippos; Luk, Wayne; Brooks, Chris (2022). "FLiMS: a Fast Lightweight 2-way Merger for Sorting". IEEE Transactions on Computers: 1–12. doi:10.1109/TC.2022.3146509. hdl:10044/1/95271. S2CID 245669103.
↑ Saitoh, Makoto; Elsayed, Elsayed A.; Chu, Thiem Van; Mashimo, Susumu; Kise, Kenji (April 2018). "A High-Performance and Cost-Effective Hardware Merge Sorter without Feedback Datapath". 2018 IEEE 26th Annual International Symposium on Field-Programmable Custom Computing Machines (FCCM). pp. 197–204. doi:10.1109/FCCM.2018.00038. ISBN 978-1-5386-5522-1. S2CID 52195866.
↑ "std:merge". cppreference.com. 2018-01-08. Retrieved 2018-04-28.
↑ "heapq — Heap queue algorithm — Python 3.10.1 documentation".

अग्रिम पठन

Donald Knuth. The Art of Computer Programming, Volume 3: Sorting and Searching, Third Edition. Addison-Wesley, 1997. ISBN 0-201-89685-0. Pages 158–160 of section 5.2.4: Sorting by Merging. Section 5.3.2: Minimum-Comparison Merging, pp. 197–207.

बाहरी संबंध

High Performance Implementation of Parallel and Serial Merge in C# with source in GitHub and in C++ GitHub

[skiena-1] 1.0 ^1.1 Skiena, Steven (2010). एल्गोरिथम डिज़ाइन मैनुअल (2nd ed.). Springer Science+Business Media. p. 123. ISBN 978-1-849-96720-4.

[toolbox-2] 2.0 ^2.1 ^2.2 Kurt Mehlhorn; Peter Sanders (2008). Algorithms and Data Structures: The Basic Toolbox. Springer. ISBN 978-3-540-77978-0.

[3] Katajainen, Jyrki; Pasanen, Tomi; Teuhola, Jukka (1996). "प्रैक्टिकल इन-प्लेस मर्जसॉर्ट". Nordic J. Computing. 3 (1): 27–40. CiteSeerX 10.1.1.22.8523.

[4] Kim, Pok-Son; Kutzner, Arne (2004). सममित तुलनाओं द्वारा स्थिर न्यूनतम संग्रहण विलय. European Symp. Algorithms. Lecture Notes in Computer Science. Vol. 3221. pp. 714–723. CiteSeerX 10.1.1.102.4612. doi:10.1007/978-3-540-30140-0_63. ISBN 978-3-540-23025-0.

[Chandramouli-5] Chandramouli, Badrish; Goldstein, Jonathan (2014). Patience is a Virtue: Revisiting Merge and Sort on Modern Processors. SIGMOD/PODS.

[greene-6] 6.0 ^6.1 ^6.2 ^6.3 Greene, William A. (1993). के-वे मर्जिंग और के-एरी सॉर्ट्स (PDF). Proc. 31-st Annual ACM Southeast Conf. pp. 127–135.

[clrs-7] 7.0 ^7.1 Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2009) [1990]. Introduction to Algorithms (3rd ed.). MIT Press and McGraw-Hill. ISBN 0-262-03384-4.

[vjd-8] Victor J. Duvanenko (2011), "Parallel Merge", Dr. Dobb's Journal

[flimsj-9] 9.0 ^9.1 Papaphilippou, Philippos; Luk, Wayne; Brooks, Chris (2022). "FLiMS: a Fast Lightweight 2-way Merger for Sorting". IEEE Transactions on Computers: 1–12. doi:10.1109/TC.2022.3146509. hdl:10044/1/95271. S2CID 245669103.

[10] Saitoh, Makoto; Elsayed, Elsayed A.; Chu, Thiem Van; Mashimo, Susumu; Kise, Kenji (April 2018). "A High-Performance and Cost-Effective Hardware Merge Sorter without Feedback Datapath". 2018 IEEE 26th Annual International Symposium on Field-Programmable Custom Computing Machines (FCCM). pp. 197–204. doi:10.1109/FCCM.2018.00038. ISBN 978-1-5386-5522-1. S2CID 52195866.

[11] "std:merge". cppreference.com. 2018-01-08. Retrieved 2018-04-28.

[12] "heapq — Heap queue algorithm — Python 3.10.1 documentation".

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

v t e Sorting algorithms
Theory	Computational complexity theory Big O notation Total order Lists Inplacement Stability Comparison sort Adaptive sort Sorting network Integer sorting X + Y sorting Transdichotomous model Quantum sort
Exchange sorts	Bubble sort Cocktail shaker sort Odd–even sort Comb sort Gnome sort Proportion extend sort Quicksort Slowsort Stooge sort Bogosort
Selection sorts	Selection sort Heapsort Smoothsort Cartesian tree sort Tournament sort Cycle sort Weak-heap sort
Insertion sorts	Insertion sort Shellsort Splaysort Tree sort Library sort Patience sorting
Merge sorts	Merge sort Cascade merge sort Oscillating merge sort Polyphase merge sort
Distribution sorts	American flag sort Bead sort Bucket sort Burstsort Counting sort Interpolation sort Pigeonhole sort Proxmap sort Radix sort Flashsort
Concurrent sorts	Bitonic sorter Batcher odd–even mergesort Pairwise sorting network Samplesort
Hybrid sorts	Block merge sort Kirkpatrick–Reisch sort Timsort Introsort Spreadsort Merge-insertion sort
Other	Topological sorting Pre-topological order Pancake sorting Spaghetti sort