ब्लॉक सॉर्ट

ब्लॉक सॉर्ट
	Block sort stably sorting numbers 1 to 16.; Insertion sort groups of 16, extract two internal buffers, tag the A blocks (of size √16 = 4 each), roll the A blocks through B, locally merge them, sort the second buffer, and redistribute the buffers.
Class	Sorting algorithm
Data structure	Array
Worst-case performance	O(n log n)
Best-case performance	O(n)
Average performance	O(n log n)
Worst-case space complexity	O(1)

ब्लॉक सॉर्ट, या ब्लॉक मर्ज सॉर्ट, एक छँटाई एल्गोरिथ्म है जो कम से कम दो मर्ज एल्गोरिथ्म संचालन को सम्मिलन सॉर्ट के साथ जोड़ता है $O (n log n)$ जगह में सॉर्टिंग एल्गोरिदम#स्थिरता सॉर्टिंग। इसे इसका नाम इस अवलोकन से मिला है कि दो क्रमबद्ध सूचियों को मर्ज करना, $A$ और $B$ , तोड़ने के बराबर है $A$ समान आकार के ब्लॉकों में, प्रत्येक को सम्मिलित करते हुए $A$ ब्लॉक करें $B$ विशेष नियमों के तहत, और विलय $AB$ जोड़े।

2008 में पोक-सोन किम और अर्ने कुट्ज़नर द्वारा स्थान विलय में ओ (लॉग एन) के लिए एक व्यावहारिक एल्गोरिदम प्रस्तावित किया गया था।^[1]

सिंहावलोकन

ब्लॉक सॉर्ट का बाहरी लूप मर्ज सॉर्ट#बॉटम-अप कार्यान्वयन|बॉटम-अप मर्ज सॉर्ट के समान है, जहां सॉर्ट का प्रत्येक स्तर उपसरणी के जोड़े को मर्ज करता है, $A$ और $B$ , 1, फिर 2, फिर 4, 8, 16 और इसी तरह के आकार में, जब तक कि दोनों उपसरणी संयुक्त न हो जाएं।

विलय के बजाय $A$ और $B$ सीधे पारंपरिक तरीकों की तरह, एक ब्लॉक-आधारित मर्ज एल्गोरिदम विभाजित होता है $A$ आकार के अलग-अलग ब्लॉकों में $\sqrt A$ (जिसके परिणामस्वरूप $\sqrt A$ ब्लॉकों की संख्या भी),^[2] प्रत्येक को सम्मिलित करता है $A$ ब्लॉक करें $B$ ऐसा कि प्रत्येक का पहला मान $A$ ब्लॉक (≤) से कम या उसके बराबर है $B$ मान इसके तुरंत बाद, फिर स्थानीय रूप से प्रत्येक का विलय हो जाता है $A$ किसी के साथ ब्लॉक करें $B$ इसके और अगले के बीच का मान $A$ अवरोध पैदा करना।

चूँकि मर्ज के लिए अभी भी एक अलग बफ़र की आवश्यकता होती है जो पर्याप्त रूप से बड़ा हो $A$ ब्लॉक को मर्ज किया जाना है, सरणी के भीतर दो क्षेत्र इस उद्देश्य के लिए आरक्षित हैं (आंतरिक बफ़र्स के रूप में जाना जाता है)।^[3] पहले दो $A$ ब्लॉकों को इस प्रकार संशोधित किया जाता है कि उनमें प्रत्येक मान का पहला उदाहरण शामिल हो $A$ , यदि आवश्यक हो तो उन ब्लॉकों की मूल सामग्री को स्थानांतरित कर दिया गया। शेष $A$ फिर ब्लॉक डाले जाते हैं $B$ और स्वैप स्पेस के रूप में दो बफ़र्स में से एक का उपयोग करके विलय कर दिया गया। यह प्रक्रिया उस बफ़र में मानों को पुनर्व्यवस्थित करने का कारण बनती है।

एक बार हर $A$ और $B$ प्रत्येक का ब्लॉक $A$ और $B$ मर्ज सॉर्ट के उस स्तर के लिए उपसरणी को मर्ज कर दिया गया है, उस बफ़र में मानों को उनके मूल क्रम को पुनर्स्थापित करने के लिए सॉर्ट किया जाना चाहिए, इसलिए एक प्रविष्टि सॉर्ट लागू किया जाना चाहिए। फिर बफ़र्स में मानों को सरणी के भीतर उनकी पहली क्रमबद्ध स्थिति में पुनः वितरित किया जाता है। यह प्रक्रिया बाहरी बॉटम-अप मर्ज सॉर्ट के प्रत्येक स्तर के लिए दोहराई जाती है, जिस बिंदु पर सरणी को स्थिर रूप से सॉर्ट किया गया होगा।

एल्गोरिथम

कोड उदाहरणों में निम्नलिखित ऑपरेटरों का उपयोग किया जाता है:

\|	bitwise OR
>>	shift right
%	modulo
++ and +=	increment
[x, y)	range from ≥ x and < y
\|range\|	range.end – range.start
array[i]	i-th item of array

इसके अतिरिक्त, ब्लॉक सॉर्ट अपने समग्र एल्गोरिदम के हिस्से के रूप में निम्नलिखित परिचालनों पर निर्भर करता है:

स्वैप (कंप्यूटर विज्ञान): एक सरणी में दो मानों की स्थिति का आदान-प्रदान करें।
स्वैप एल्गोरिदम को ब्लॉक करें: किसी सरणी के भीतर मानों की एक श्रृंखला को सरणी की एक अलग श्रेणी में मानों के साथ विनिमय करें।
बाइनरी खोज एल्गोरिदम: यह मानते हुए कि सरणी क्रमबद्ध है, वर्तमान खोज श्रेणी के मध्य मान की जांच करें, फिर यदि मान कम है तो निचली श्रेणी की जांच करें, और यदि मान अधिक है तो ऊपरी श्रेणी की जांच करें। ब्लॉक सॉर्ट दो वेरिएंट का उपयोग करता है: एक जो सॉर्ट किए गए सरणी में मान डालने के लिए पहली स्थिति ढूंढता है, और एक जो अंतिम स्थिति ढूंढता है।
रैखिक खोज: किसी सरणी में प्रत्येक तत्व को क्रम से जांचकर एक विशेष मान ढूंढें, जब तक कि वह न मिल जाए।
सम्मिलन प्रकार: सरणी में प्रत्येक आइटम के लिए, पीछे की ओर लूप करें और पता लगाएं कि इसे कहां सम्मिलित करने की आवश्यकता है, फिर इसे उस स्थान पर डालें।
ऐरे रोटेशन: किसी ऐरे में आइटमों को बाईं या दाईं ओर कुछ स्थानों पर ले जाएं, किनारों पर मानों को दूसरी तरफ लपेटते हुए। रोटेशन को तीन इन-प्लेस एल्गोरिदम#उदाहरण के रूप में कार्यान्वित किया जा सकता है।^[4]

घुमाएँ (सरणी, राशि, सीमा)

    रिवर्स (सरणी, रेंज)
    रिवर्स (सरणी, [रेंज.स्टार्ट, रेंज.स्टार्ट + राशि))
    रिवर्स(सरणी, [रेंज.स्टार्ट + राशि, रेंज.एंड))

दो की फर्श शक्ति: फर्श और छत दो की अगली शक्ति के मान पर कार्य करते हैं। इस प्रकार 63 32 हो जाता है, 64 64 ही रहता है, इत्यादि।^[5]

फ़्लोरपावरऑफ़टू(x)
    एक्स = एक्स | (एक्स >> 1)
    एक्स = एक्स | (एक्स >> 2)
    एक्स = एक्स | (x>4)
    एक्स = एक्स | (x >> 8)
    एक्स = एक्स | (x >> 16)
    यदि (यह 64-बिट कंप्यूटिंग|64-बिट सिस्टम है)
        एक्स = एक्स | (x>32)
    वापसी x - (x >> 1)

बाहरी लूप

जैसा कि पहले बताया गया है, ब्लॉक सॉर्ट का बाहरी लूप बॉटम-अप मर्ज सॉर्ट के समान है। हालाँकि, यह उस वैरिएंट से लाभान्वित होता है जो प्रत्येक को सुनिश्चित करता है A और B उपसरणी एक आइटम के भीतर समान आकार की होती है:

   ब्लॉकसॉर्ट(सरणी)
       पॉवर_ऑफ़_टू = फ़्लोरपावरऑफ़टू(सरणी.आकार)
       स्केल = array.size/power_of_two // 1.0 ≤ स्केल <2.0
      
       <स्पैन स्टाइल=रंग:हरा; >// प्रविष्टि एक समय में 16-31 आइटमों को क्रमबद्ध करती है
       के लिए (विलय = 0; विलय <power_of_two; विलय += 16)
           प्रारंभ = मर्ज * स्केल
           अंत = प्रारंभ + 16 * पैमाना
           सम्मिलन सॉर्ट (सरणी, [प्रारंभ, अंत))
      
       (लंबाई = 16; लंबाई < शक्ति_दो_के लिए; लंबाई += लंबाई) के लिए
           के लिए (विलय = 0; विलय <power_of_two; विलय += लंबाई * 2)
               प्रारंभ = मर्ज * स्केल
               मध्य = (विलय + लंबाई) * पैमाना
               अंत = (विलय + लंबाई * 2) * पैमाना
              
               यदि (सरणी[अंत − 1] <सरणी[प्रारंभ])
                   <स्पैन स्टाइल=रंग:हरा; >// दोनों श्रेणियां उल्टे क्रम में हैं, इसलिए उन्हें मिलाने के लिए एक रोटेशन पर्याप्त है
                   घुमाएँ (सरणी, मध्य - प्रारंभ, [प्रारंभ, अंत))
               अन्यथा यदि (सरणी[मध्य − 1] > सारणी[मध्य])
                   मर्ज (सरणी, ए = [प्रारंभ, मध्य), बी = [मध्य, अंत))
               <स्पैन स्टाइल=रंग:हरा; >// अन्यथा श्रेणियाँ पहले से ही सही ढंग से क्रमबद्ध हैं

निश्चित-बिंदु अंकगणित|पैमाने के कारक को अंश के रूप में प्रस्तुत करके निश्चित-बिंदु गणित का भी उपयोग किया जा सकता है integer_part + numerator/denominator:

   पॉवर_ऑफ़_टू = फ़्लोरपावरऑफ़टू(सरणी.आकार)
   हर = घात_दो/16
   numerator_step = array.size % denominator
   पूर्णांक_चरण = मंजिल(सरणी.आकार/भाजक)
  
   <स्पैन स्टाइल=रंग:हरा; >// प्रविष्टि एक समय में 16-31 आइटमों को क्रमबद्ध करती है
  
   जबकि (पूर्णांक_चरण < array.size)
       पूर्णांक_भाग = अंश = 0
       जबकि (पूर्णांक_भाग < array.size)
           <स्पैन स्टाइल=रंग:हरा; >//ए और बी के लिए श्रेणियां प्राप्त करें
           प्रारंभ = पूर्णांक_भाग
          
           पूर्णांक_भाग += पूर्णांक_चरण
           अंश += अंशांकक_चरण
           यदि (अंश ≥ हर)
               अंश −= हर
               पूर्णांक_भाग++
          
           मध्य = पूर्णांक_भाग
          
           पूर्णांक_भाग += पूर्णांक_चरण
           अंश += अंशांकक_चरण
           यदि (अंश ≥ हर)
               अंश −= हर
               पूर्णांक_भाग++
          
           अंत = पूर्णांक_भाग
          
           यदि (सरणी[अंत − 1] <सरणी[प्रारंभ])
               घुमाएँ (सरणी, मध्य - प्रारंभ, [प्रारंभ, अंत))
           अन्यथा यदि (सरणी[मध्य − 1] > सारणी[मध्य])
               मर्ज (सरणी, ए = [प्रारंभ, मध्य), बी = [मध्य, अंत))
      
       पूर्णांक_चरण += पूर्णांक_चरण
       numerator_step += numerator_step
       यदि (अंशांक_चरण ≥ हर)
           numerator_step −= हर
           पूर्णांक_चरण++

बफ़र्स निकालें

File:Buffer extraction for block sort.gif

ब्लॉक सॉर्ट के लिए बफ़र निष्कर्षण प्रक्रिया।

मर्ज चरण के प्रत्येक स्तर के लिए आवश्यक दो आंतरिक बफ़र्स पहले 2 को स्थानांतरित करके बनाए जाते हैं√A एक के भीतर उनके मूल्यों का पहला उदाहरण A की शुरुआत तक उपसरणी A. सबसे पहले यह तत्वों पर पुनरावृति करता है A और इसके लिए आवश्यक अद्वितीय मानों की गणना करता है, फिर यह उन अद्वितीय मानों को प्रारंभ में ले जाने के लिए सरणी घुमाव लागू करता है।^[6] यदि A में दो बफ़र्स (आकार के) को भरने के लिए पर्याप्त अद्वितीय मान नहीं हैं √A प्रत्येक), B का भी उपयोग किया जा सकता है। इस स्थिति में यह प्रत्येक मान के अंतिम उदाहरण को अंत तक ले जाता है B, के उस भाग के साथ B विलय के दौरान शामिल नहीं किया जा रहा है।

जबकि (पूर्णांक_चरण < array.size)
    ब्लॉक_आकार = √integer_step
    बफ़र_साइज़ = पूर्णांक_स्टेप/ब्लॉक_साइज़ + 1
    <स्पैन स्टाइल=रंग:हरा; >[प्रत्येक 'buffer_size' आकार के दो बफ़र्स निकालें]

अगर B में पर्याप्त अद्वितीय मान भी नहीं हैं, यह जितनी बड़ी संख्या में अद्वितीय मान पा सकता था उसे निकालता है, फिर के आकार को समायोजित करता है A और B ऐसे ब्लॉक करता है कि परिणाम की संख्या A ब्लॉक बफ़र के लिए निकाली गई अद्वितीय वस्तुओं की संख्या से कम या उसके बराबर है। इस मामले में केवल एक बफ़र का उपयोग किया जाएगा - दूसरा बफ़र मौजूद नहीं होगा।

बफ़र_आकार = <स्पैन शैली = रंग: हरा; >[अनूठे मूल्यों की संख्या मिली]
ब्लॉक_साइज़ = पूर्णांक_स्टेप/बफ़र_साइज़ + 1
  
पूर्णांक_भाग = अंश = 0
जबकि (पूर्णांक_भाग < array.size)
    <स्पैन स्टाइल=रंग:हरा; >[ए और बी के लिए श्रेणियां प्राप्त करें]
    <स्पैन स्टाइल=रंग:हरा; >[ए और बी को समायोजित करें ताकि बफ़र्स द्वारा उपयोग की जाने वाली श्रेणियां शामिल न हों]

टैग ए ब्लॉक

File:Block sort tagging A blocks.gif

टैग कर रहा हूँ A पहले आंतरिक बफ़र से मानों का उपयोग करके ब्लॉक करता है। ध्यान दें कि सबसे पहले A ब्लॉक और अंतिम B ब्लॉक असमान आकार के हैं।

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

<स्पैन स्टाइल=रंग:हरा; >// ब्लॉकए शेष ए ब्लॉक की सीमा है,
<स्पैन स्टाइल=रंग:हरा; >// और फर्स्टए असमान आकार का पहला ए ब्लॉक है
ब्लॉकए = [ए.स्टार्ट, ए.एंड)
फर्स्टए = [ए.स्टार्ट, ए.स्टार्ट + |ब्लॉकए| % ब्लॉक का आकार)
  
<स्पैन स्टाइल=रंग:हरा; >// प्रत्येक ए ब्लॉक के दूसरे मान को बफ़र1 के मान के साथ स्वैप करें
'के लिए' (इंडेक्स = 0, इंडेक्सए = फर्स्टए.एंड + 1; इंडेक्सए < ब्लॉकए.एंड; इंडेक्सए += ब्लॉक_साइज)
    'स्वैप'(सरणी[बफ़र1.स्टार्ट + इंडेक्स], सरणी[इंडेक्सए])
    सूचकांक++
  
अंतिमए = प्रथमए
ब्लॉकबी = [बी.स्टार्ट, बी.स्टार्ट + 'न्यूनतम'(ब्लॉक_आकार, |बी|))
ब्लॉकए.स्टार्ट += |फर्स्टए|

लुढ़कना और गिराना

File:Block sort roll and drop.gif

दो ए ब्लॉक बी ब्लॉक से होकर गुजर रहे हैं। एक बार जब पहला ए ब्लॉक पीछे छूट जाता है, तो असमान आकार का ए ब्लॉक स्थानीय रूप से उसके बाद आने वाले बी मानों के साथ विलय हो जाता है।

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

उस समय, न्यूनतम ए ब्लॉक (सबसे छोटे टैग मान वाला ए ब्लॉक) को रोलिंग ए ब्लॉक की शुरुआत में बदल दिया जाता है और टैग किए गए मान को पहले बफर से उसके मूल मान के साथ बहाल किया जाता है। इसे एक ब्लॉक को पीछे छोड़ने के रूप में जाना जाता है, क्योंकि इसे अब शेष ए ब्लॉक के साथ रोल नहीं किया जाएगा। उस A ब्लॉक को पिछले B ब्लॉक में डाला जाता है, पहले B पर बाइनरी सर्च का उपयोग करके उस इंडेक्स को ढूंढा जाता है जहां A का पहला मान B के उस इंडेक्स के मान से कम या उसके बराबर है, और फिर A को इसमें घुमाकर उस सूचकांक पर बी.

   मिनए = ब्लॉकए.स्टार्ट
   इंडेक्सए = 0
  
   'जबकि' (सच)
       <स्पैन स्टाइल=रंग:हरा; >// यदि पिछला बी ब्लॉक है और न्यूनतम ए ब्लॉक का पहला मान ≤ है
       <स्पैन स्टाइल=रंग:हरा; >// पिछले B ब्लॉक का अंतिम मान, फिर उस न्यूनतम A ब्लॉक को पीछे छोड़ दें।
       <स्पैन स्टाइल=रंग:हरा; >//या यदि कोई बी ब्लॉक नहीं बचा है तो शेष ए ब्लॉक गिराते रहें।
       'if' ((|lastB| > 0 'and' array[lastB.end - 1] ≥ array[minA]) 'or' |blockB| = 0)
           <स्पैन स्टाइल=रंग:हरा; >// पता लगाएं कि पिछले बी ब्लॉक को कहां विभाजित करना है, और इसे विभाजन पर घुमाएं
           B_split = 'बाइनरीफर्स्ट'(सरणी, सारणी[minA], अंतिमबी)
           B_शेष = अंतिमB.अंत - B_विभाजित
          
           <स्पैन स्टाइल=रंग:हरा; >// रोलिंग ए ब्लॉक की शुरुआत में न्यूनतम ए ब्लॉक को स्वैप करें
           'ब्लॉकस्वैप'(सरणी, ब्लॉकए.स्टार्ट, मिनए, ब्लॉक_आकार)
          
           <स्पैन स्टाइल=रंग:हरा; >// ए ब्लॉक के लिए दूसरा मान पुनर्स्थापित करें
           'स्वैप'(सरणी[ब्लॉकए.स्टार्ट + 1], सरणी[बफर1.स्टार्ट + इंडेक्सए])
           इंडेक्सए++
          
           <स्पैन स्टाइल=रंग:हरा; >// A ब्लॉक को पिछले B ब्लॉक में घुमाएँ
           'घुमाएँ'(सरणी, ब्लॉकए.स्टार्ट - बी_स्प्लिट, [बी_स्प्लिट, ब्लॉकए.स्टार्ट + ब्लॉक_साइज))
          
           <स्पैन स्टाइल=रंग:हरा; >//स्थानीय रूप से पिछले ए ब्लॉक को उसके बाद आने वाले बी मानों के साथ मर्ज करें,
           <स्पैन स्टाइल=रंग:हरा; >// दूसरे आंतरिक बफ़र को स्वैप स्पेस के रूप में उपयोग करना (यदि यह मौजूद है)
           'अगर' (|बफर2| > 0)
               'मर्जइंटरनल'(सरणी, लास्टए, [लास्टए.एंड, बी_स्प्लिट), बफर2)
           'अन्य'
               'मर्जइनप्लेस'(सरणी, लास्टए, [लास्टए.एंड, बी_स्प्लिट))
          
           <स्पैन स्टाइल=रंग:हरा; >// शेष ए ब्लॉक के लिए सीमा को अपडेट करें,
           <स्पैन स्टाइल=रंग:हरा; >// और बी ब्लॉक के विभाजन के बाद बची हुई सीमा
           अंतिमए = [ब्लॉकए.स्टार्ट - बी_शेष, ब्लॉकए.स्टार्ट - बी_शेष + ब्लॉक_आकार)
           अंतिमबी = [अंतिमए.अंत, अंतिमए.अंत + बी_शेष)
          
           <स्पैन स्टाइल=रंग:हरा; >// यदि कोई और ए ब्लॉक शेष नहीं है, तो यह चरण समाप्त हो गया है
           ब्लॉकए.स्टार्ट = ब्लॉकए.स्टार्ट + ब्लॉक_आकार
           'अगर' (|ब्लॉकए| = 0)
               'तोड़ना'
          
           minA = [नया न्यूनतम ए ब्लॉक] (नीचे देखें)
       'अन्यथा यदि' (|ब्लॉकबी| <ब्लॉक_आकार)
           <स्पैन स्टाइल=रंग:हरा; >//अंतिम बी ब्लॉक को स्थानांतरित करें, जिसका आकार असमान है,
           <स्पैन स्टाइल=रंग:हरा; >// शेष ए ब्लॉक से पहले, एक रोटेशन का उपयोग करके
           'घुमाएँ'(सरणी, ब्लॉकबी.स्टार्ट - ब्लॉकए.स्टार्ट, [ब्लॉकए.स्टार्ट, ब्लॉकबी.एंड))
          
           लास्टबी = [ब्लॉकए.स्टार्ट, ब्लॉकए.स्टार्ट + |ब्लॉकबी|)
           ब्लॉकए.स्टार्ट += |ब्लॉकबी|
           ब्लॉकए.एंड += |ब्लॉकबी|
           minA += |ब्लॉकबी|
           ब्लॉकबी.एंड = बीएलओकेबी.स्टार्ट
       'अन्य'
           <स्पैन स्टाइल=रंग:हरा; >// सबसे बाएं ए ब्लॉक को अगले बी ब्लॉक के साथ स्वैप करके अंत तक रोल करें
           'ब्लॉकस्वैप'(सरणी, ब्लॉकए.स्टार्ट, ब्लॉकबी.स्टार्ट, ब्लॉक_साइज)
           लास्टबी = [ब्लॉकए.स्टार्ट, ब्लॉकए.स्टार्ट + ब्लॉक_साइज)
           'अगर' (मिनए = ब्लॉकए.स्टार्ट)
               minA = ब्लॉकए.एंड
          
           ब्लॉकए.स्टार्ट += ब्लॉक_आकार
           ब्लॉकए.एंड += ब्लॉक_आकार
           ब्लॉकबी.स्टार्ट += ब्लॉक_आकार
          
           <स्पैन स्टाइल=रंग:हरा; >// यह 'न्यूनतम' (ब्लॉकबी.एंड + ब्लॉक_साइज, बी.एंड) के बराबर है,
           <स्पैन स्टाइल=रंग:हरा; >// लेकिन इसमें पूर्णांक अतिप्रवाह की संभावना है
           'अगर' (ब्लॉकबी.एंड > बी.एंड - ब्लॉक_आकार)
               ब्लॉकबी.एंड = बी.एंड
           'अन्य'
               ब्लॉकबी.एंड += ब्लॉक_आकार
  
   <स्पैन स्टाइल=रंग:हरा; >// अंतिम A ब्लॉक को शेष B मानों के साथ मर्ज करें
   'अगर' (|बफर2| > 0)
       'मर्जइंटरनल'(सरणी, लास्टए, [लास्टए.एंड, बी.एंड), बफर2)
   'अन्य'
       'मर्जइनप्लेस'(सरणी, लास्टए, [लास्टए.एंड, बी.एंड))

एक अनुकूलन जिसे इस चरण के दौरान लागू किया जा सकता है वह है फ्लोटिंग-होल तकनीक।^[7] जब न्यूनतम ए ब्लॉक को पीछे छोड़ दिया जाता है और उसे पिछले बी ब्लॉक में घुमाने की आवश्यकता होती है, जिसके बाद इसकी सामग्री को स्थानीय विलय के लिए दूसरे आंतरिक बफर में बदल दिया जाता है, तो ए ब्लॉक को पहले से ही बफर में स्वैप करना तेज़ होगा, और इस तथ्य का लाभ उठाने के लिए कि उस बफ़र की सामग्री को कोई ऑर्डर बनाए रखने की आवश्यकता नहीं है। इसलिए स्थिति सूचकांक पर दूसरे बफ़र (जो ब्लॉक स्वैप से पहले ए ब्लॉक हुआ करता था) को पिछले बी ब्लॉक में घुमाने के बजाय, सूचकांक के बाद बी ब्लॉक में मानों को बस बफ़र के अंतिम आइटम के साथ ब्लॉक स्वैप किया जा सकता है।

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

स्थानीय विलय

एक बार जब ए ब्लॉक को बी ब्लॉक में घुमाया जाता है, तो पिछले ए ब्लॉक को उसके बाद आने वाले बी मानों के साथ विलय कर दिया जाता है, दूसरे बफर को स्वैप स्पेस के रूप में उपयोग किया जाता है। जब पहला ए ब्लॉक पीछे गिराया जाता है तो इसका मतलब शुरुआत में असमान आकार का ए ब्लॉक होता है, जब दूसरा ए ब्लॉक उसके पीछे गिराया जाता है तो इसका मतलब पहला ए ब्लॉक होता है, इत्यादि।

मर्जइंटरनल (सरणी, ए, बी, बफर)
    <स्पैन स्टाइल=रंग:हरा; >// ए में मानों को 'बफ़र' में मौजूद मानों के साथ ब्लॉक करें
    ब्लॉकस्वैप(सरणी, ए.स्टार्ट, बफर.स्टार्ट, |ए|)

    A_count = 0, B_count = 0, सम्मिलित करें = 0
    जबकि (A_count < |A| और B_count < |B|)
        यदि (सरणी[बफर.स्टार्ट + ए_काउंट] ≤ ऐरे[बी.स्टार्ट + बी_काउंट])
            स्वैप (सरणी[ए.स्टार्ट + इंसर्ट], सरणी[बफर.स्टार्ट + ए_काउंट])
            A_गिनती++
        अन्य
            स्वैप (सरणी[ए.स्टार्ट + इंसर्ट], सरणी[बी.स्टार्ट + बी_काउंट])
            B_गिनती++
        सम्मिलित करें++

    <स्पैन स्टाइल=रंग:हरा; >// ब्लॉक बफ़र के शेष भाग को सरणी के शेष भाग के साथ स्वैप करें
    ब्लॉकस्वैप(सरणी, बफ़र.स्टार्ट + ए_काउंट, ए.स्टार्ट + इंसर्ट, |ए| - ए_काउंट)

यदि दूसरा बफ़र मौजूद नहीं है, तो एक सख्ती से इन-प्लेस मर्ज ऑपरेशन किया जाना चाहिए, जैसे कि ह्वांग और लिन एल्गोरिदम का रोटेशन-आधारित संस्करण,^[7]^[8] डुडज़िंस्की और डायडेक एल्गोरिदम,^[9] या बार-बार बाइनरी खोज और घुमाएँ।

मर्जइनप्लेस(सरणी, ए, बी)
    जबकि (|ए| > 0 और |बी| > 0)
        <स्पैन स्टाइल=रंग:हरा; >// B में पहला स्थान ढूंढें जहां A में पहला आइटम डालने की आवश्यकता है
        मध्य = बाइनरीफर्स्ट(सरणी, सारणी[ए.स्टार्ट], बी)

        <स्पैन स्टाइल=रंग:हरा; >// A को स्थान पर घुमाएँ
        राशि = मध्य - ए.अंत
        घुमाएँ(सरणी, राशि, [ए.प्रारंभ, मध्य))

        <स्पैन स्टाइल=रंग:हरा; >// नई ए और बी श्रेणियों की गणना करें
        बी = [मध्य, बी.अंत)
        ए = [ए. प्रारंभ + राशि, मध्य)
        ए.स्टार्ट = बाइनरीलास्ट(सरणी, सरणी[ए.स्टार्ट], ए)

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

मिनए = ब्लॉकए.स्टार्ट
के लिए (findA = minA + ब्लॉक_आकार; findA < ब्लॉकA.end - 1; findA += ब्लॉक_आकार)
    यदि (सरणी[ढूंढेंए + 1] <सरणी[मिनए + 1])
        minA = ढूंढेंA

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

एक बार जब अंतिम शेष A ब्लॉक को पीछे छोड़ दिया जाता है और B में डाल दिया जाता है, तो इसे इसके बाद आने वाले शेष B मानों के साथ विलय कर दिया जाना चाहिए। यह ए और बी उपसरणी की उस विशेष जोड़ी के लिए मर्ज प्रक्रिया को पूरा करता है। हालाँकि, इसे मर्ज सॉर्ट के वर्तमान स्तर के लिए शेष ए और बी उपसरणी के लिए प्रक्रिया को दोहराना होगा।

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

पुनर्वितरित

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

बॉटम-अप मर्ज सॉर्ट के प्रत्येक स्तर के लिए इन चरणों को दोहराने के बाद, ब्लॉक सॉर्ट पूरा हो जाता है।

वेरिएंट

ब्लॉक सॉर्ट दो आंतरिक बफ़र्स को निकालकर, ए और बी उपसरणी को समान आकार के ब्लॉक में तोड़कर, ए ब्लॉक को बी में रोल और ड्रॉप करके (ए ब्लॉक के ऑर्डर को ट्रैक करने के लिए पहले बफर का उपयोग करके), दूसरे बफर को स्वैप के रूप में उपयोग करके स्थानीय रूप से विलय करके काम करता है। स्थान, दूसरे बफ़र को सॉर्ट करना, और दोनों बफ़र्स को पुनर्वितरित करना। हालाँकि चरण नहीं बदलते हैं, ये उपप्रणालियाँ अपने वास्तविक कार्यान्वयन में भिन्न हो सकती हैं।

ब्लॉक सॉर्ट का एक संस्करण इसे प्रदान की गई अतिरिक्त मेमोरी की किसी भी मात्रा का उपयोग करने की अनुमति देता है, जब भी ए इसमें फिट बैठता है तो ए उपसरणी या ए ब्लॉक को बी के साथ विलय करने के लिए इस बाहरी बफर का उपयोग करता है। इस स्थिति में यह मर्ज सॉर्ट के समान होगा।

बफ़र आकार के लिए अच्छे विकल्पों में शामिल हैं:

Size	Notes
(count + 1)/2	turns into a full-speed merge sort since all of the A subarrays will fit into it
√(count + 1)/2 + 1	this will be the size of the A blocks at the largest level of merges, so block sort can skip using internal or in-place merges for anything
512	a fixed-size buffer large enough to handle the numerous merges at the smaller levels of the merge sort
0	if the system cannot allocate any extra memory, no memory works well

आंतरिक बफ़र्स में से किसी एक की सामग्री का उपयोग करके ए ब्लॉक को टैग करने के बजाय, एक अप्रत्यक्ष आंदोलन-अनुकरण बफ़र का उपयोग किया जा सकता है।^[1]^[10] यह एक आंतरिक बफर है जिसे s1 t s2 के रूप में परिभाषित किया गया है, जहां s1 और s2 प्रत्येक ए और बी ब्लॉक की संख्या के बराबर बड़े हैं, और टी में s1 के तुरंत बाद कोई भी मान शामिल है जो s1 के अंतिम मान के बराबर है (इस प्रकार यह सुनिश्चित होता है कि कोई नहीं) s2 में मान s1 में दिखाई देता है)। एक दूसरा आंतरिक बफ़र युक्त √A अद्वितीय मान अभी भी उपयोग किया जाता है। पहला √A फिर s1 और s2 के मानों को बफर में जानकारी एन्कोड करने के लिए एक दूसरे के साथ स्वैप किया जाता है कि कौन से ब्लॉक A ब्लॉक हैं और कौन से B ब्लॉक हैं। जब इंडेक्स i पर A ब्लॉक को इंडेक्स j पर B ब्लॉक के साथ स्वैप किया जाता है (जहां पहला समान आकार का A ब्लॉक प्रारंभ में इंडेक्स 0 पर होता है), s1[i] और s1[j] को s2[i] और s2[ के साथ स्वैप किया जाता है। जे], क्रमशः। यह बी के माध्यम से ए ब्लॉक की गतिविधियों का अनुकरण करता है। दूसरे बफर में अद्वितीय मानों का उपयोग ए ब्लॉक के मूल क्रम को निर्धारित करने के लिए किया जाता है क्योंकि उन्हें बी ब्लॉक के माध्यम से घुमाया जाता है। एक बार जब सभी ए ब्लॉक हटा दिए जाते हैं, तो मूवमेंट-इमिटेशन बफर का उपयोग यह डिकोड करने के लिए किया जाता है कि सरणी में दिया गया ब्लॉक ए ब्लॉक है या बी ब्लॉक, प्रत्येक ए ब्लॉक को बी में घुमाया जाता है, और दूसरे आंतरिक बफर का उपयोग किया जाता है स्थानीय विलयों के लिए स्वैप स्थान के रूप में।

प्रत्येक ए ब्लॉक के दूसरे मान को टैग करने की आवश्यकता नहीं है - इसके बजाय पहले, आखिरी, या किसी अन्य तत्व का उपयोग किया जा सकता है। हालाँकि, यदि पहला मान टैग किया गया है, तो न्यूनतम ए ब्लॉक को कहां छोड़ना है, यह तय करते समय मानों को पहले आंतरिक बफर (जहां उन्हें स्वैप किया गया था) से पढ़ने की आवश्यकता होगी।

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

विश्लेषण

ब्लॉक सॉर्ट एल्गोरिदम का एक अच्छी तरह से परिभाषित और परीक्षण योग्य वर्ग है, जिसमें मर्ज और सॉर्ट के रूप में कार्यशील कार्यान्वयन उपलब्ध हैं।^[11]^[12]^[13] इससे इसकी विशेषताओं को मापने और विचार करने की अनुमति मिलती है।

जटिलता

ब्लॉक सॉर्ट की शुरुआत सरणी में 16-31 आइटमों के समूहों पर इंसर्शन सॉर्ट करने से होती है। सम्मिलन सॉर्ट एक है $O(n^{2})$ ऑपरेशन, इसलिए यह कहीं से भी ले जाता है $O(16^{2}\times n/16)$ को $O(31^{2}\times n/31)$ , जो है $O(n)$ एक बार बिग ओ नोटेशन#उदाहरण। विलय के प्रत्येक स्तर के पूरा होने के बाद इसे दूसरे आंतरिक बफ़र पर एक प्रविष्टि सॉर्ट भी लागू करना होगा। हालाँकि, चूँकि यह बफ़र सीमित था ${\sqrt {A}}$ आकार में, $O{\sqrt {n}}^{2}$ ऑपरेशन भी ख़त्म हो जाता है $O(n)$ .

इसके बाद इसे मर्ज सॉर्ट के प्रत्येक स्तर के लिए दो आंतरिक बफ़र्स निकालने होंगे। यह ए और बी उपसरणी में आइटमों पर पुनरावृत्ति करके और जब भी मूल्य बदलता है तो काउंटर बढ़ाकर ऐसा करता है, और पर्याप्त मान मिलने पर यह उन्हें ए की शुरुआत या बी के अंत में घुमाता है। सबसे खराब स्थिति में यह समाप्त हो जाएगा खोजने से पहले संपूर्ण सरणी को खोजना ${\sqrt {A}}$ गैर-सन्निहित अद्वितीय मान, जिसकी आवश्यकता है $O(n)$ तुलना और ${\sqrt {A}}$ के लिए घूर्णन ${\sqrt {A}}$ मूल्य. इसका समाधान होता है $O(n+{\sqrt {n}}\times {\sqrt {n}})$ , या $O(n)$ .

जब ए या बी उपसरणी में से कोई भी शामिल नहीं है ${\sqrt {A}}$ आंतरिक बफ़र्स बनाने के लिए अद्वितीय मान, एक सामान्य रूप से उप-इष्टतम इन-प्लेस मर्ज ऑपरेशन किया जाता है जहां यह बार-बार बाइनरी खोज करता है और ए को बी में घुमाता है। हालांकि, किसी भी उपसरणी के भीतर अद्वितीय मानों की ज्ञात कमी संख्या पर एक कठिन सीमा लगाती है बाइनरी खोज और रोटेशन जो इस चरण के दौरान किए जाएंगे, जो कि फिर से है ${\sqrt {A}}$ तक आइटम घुमाए गए ${\sqrt {A}}$ समय, या $O(n)$ . प्रत्येक ब्लॉक का आकार भी उस स्थिति में छोटा करने के लिए समायोजित किया जाता है जहां यह पाया जाता है ${\sqrt {A}}$ अद्वितीय मान लेकिन नहीं 2 ${\sqrt {A}}$ , जो किसी ए या बी ब्लॉक में निहित अद्वितीय मानों की संख्या को और सीमित कर देता है।

ए ब्लॉक को टैग करने का कार्य किया जाता है ${\sqrt {A}}$ प्रत्येक ए उपसरणी के लिए कई बार, फिर ए ब्लॉक को रोल किया जाता है और बी ब्लॉक में डाला जाता है ${\sqrt {A}}$ बार. स्थानीय मर्ज वही रहते हैं $O(n)$ एक मानक मर्ज की जटिलता, हालांकि अधिक असाइनमेंट के साथ, क्योंकि मूल्यों को कॉपी करने के बजाय स्वैप किया जाना चाहिए। नए न्यूनतम ए ब्लॉक को खोजने के लिए रैखिक खोज पुनरावृत्त होती है ${\sqrt {A}}$ ब्लाकों ${\sqrt {A}}$ बार. और बफ़र पुनर्वितरण प्रक्रिया बफ़र निष्कर्षण के समान है लेकिन विपरीत है, और इसलिए समान है $O(n)$ जटिलता.

बिग ओ नोटेशन#उदाहरण के बाद और उस पर विचार करते हुए $\log {n}$ बाहरी मर्ज लूप में स्तर, यह अंतिम स्पर्शोन्मुख जटिलता की ओर ले जाता है $O(n\log {n})$ सबसे खराब और औसत मामलों के लिए. सर्वोत्तम स्थिति के लिए, जहां डेटा पहले से ही क्रम में है, मर्ज चरण निष्पादित होता है $n/16$ फिर, पहले स्तर के लिए तुलना $n/32$ , $n/64$ , $n/128$ , आदि। यह 1/2 + 1/4 + 1/8 + 1/16 + · ··||प्रसिद्ध गणितीय श्रृंखला है जो हल करती है $O(n)$ .

मेमोरी

चूंकि ब्लॉक सॉर्ट रिकर्सन (कंप्यूटर विज्ञान) | गैर-पुनरावर्ती है और इसमें मेमोरी प्रबंधन # मैन्युअल मेमोरी प्रबंधन के उपयोग की आवश्यकता नहीं होती है, इससे निरंतर स्टैक (अमूर्त डेटा प्रकार) और हीप स्पेस होता है। यह ट्रांसडिकोटोमस मॉडल में O(1) सहायक मेमोरी का उपयोग करता है, जो स्वीकार करता है कि A और B के लिए रेंज का ट्रैक रखने के लिए आवश्यक O(लॉग एन) बिट्स 32-बिट या 64-बिट पर 32 या 64 से अधिक नहीं हो सकते हैं। कंप्यूटिंग सिस्टम, क्रमशः, और इसलिए किसी भी सरणी के लिए O(1) स्थान को सरल बनाता है जिसे संभवतः आवंटित किया जा सकता है।

स्थिरता

यद्यपि ब्लॉक सॉर्ट के दौरान सरणी में आइटम क्रम से बाहर हो जाते हैं, प्रत्येक ऑपरेशन पूरी तरह से उलटा होता है और इसके पूरा होने पर समकक्ष आइटम के मूल क्रम को बहाल कर दिया जाएगा।

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

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

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

अनुकूलता

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

लाभ

ब्लॉक सॉर्ट एक स्थिर सॉर्ट है जिसमें अतिरिक्त मेमोरी की आवश्यकता नहीं होती है, जो उन मामलों में उपयोगी है जहां ओ (एन) बफर आवंटित करने के लिए पर्याप्त मुफ्त मेमोरी नहीं है। ब्लॉक सॉर्ट के बाहरी बफ़र संस्करण का उपयोग करते समय, यह आवश्यकतानुसार O(n) मेमोरी का उपयोग करके उत्तरोत्तर छोटे बफ़र्स तक स्केल कर सकता है, और फिर भी उन बाधाओं के भीतर कुशलता से काम करेगा।

नुकसान

ब्लॉक सॉर्ट डेटा की सॉर्ट की गई श्रेणियों का उतने अच्छे स्तर पर शोषण नहीं करता है जितना कि कुछ अन्य एल्गोरिदम, जैसे कि टिमसॉर्ट।^[14] यह केवल दो पूर्वनिर्धारित स्तरों पर इन क्रमबद्ध श्रेणियों की जाँच करता है: ए और बी उपसरणी, और ए और बी ब्लॉक। मर्ज सॉर्ट की तुलना में इसे लागू करना और समानांतर बनाना भी कठिन है।

संदर्भ

↑ ^1.0 ^1.1 Kutzner, Arne; Kim, Pok-Son (2008). अनुपात आधारित स्थिर इन-प्लेस विलय (PDF). Lecture Notes in Computer Science. Vol. 4978. Springer Berlin Heidelberg. pp. 246–257. Retrieved 2016-09-07.
↑ Mannila, Heikki; Ukkonen, Esko (14 May 1984). "इन-सीटू विलय के लिए एक सरल रैखिक समय एल्गोरिदम". Information Processing Letters. 18 (4): 203–208. doi:10.1016/0020-0190(84)90112-1.
↑ Kronrod, M. Alexander (February 1969). "Оптимальный алгоритм упорядочения без рабочего поля" [An Optimal Ordering Algorithm without a Field of Operation]. Proceedings of the USSR Academy of Sciences (in русский). 186 (6): 1256–1258.
↑ Bentley, Jon (2006). प्रोग्रामिंग मोती (2nd ed.).
↑ Warren Jr., Henry S. (2013) [2002]. हैकर की प्रसन्नता (2 ed.). Addison Wesley - Pearson Education, Inc. ISBN 978-0-321-84268-8. 0-321-84268-5.
↑ Pardo, Luis Trabb (1977). इष्टतम स्थान और समय सीमा के साथ स्थिर छँटाई और विलय. SIAM Journal on Computing. Vol. 6. pp. 351–372.
↑ ^7.0 ^7.1 Geffert, Viliam; Katajainen, Jykri; Pasanen, Tomi (April 2000). "असम्बद्ध रूप से कुशल इन-प्लेस विलय". Theoretical Computer Science. 237 (1–2): 159–181. CiteSeerX 10.1.1.22.5750. doi:10.1016/S0304-3975(98)00162-5.
↑ Hwang, F. K.; Lin, S. (1972). दो असंयुक्त रैखिक क्रमित सेटों को मर्ज करने के लिए एक सरल एल्गोरिदम. SIAM Journal on Computing. Vol. 1. pp. 31–39. doi:10.1137/0201004. ISSN 0097-5397.
↑ Dudzinski, Krzysztof; Dydek, Andrzej (1981). एक स्थिर भंडारण विलय एल्गोरिदम पर. Information Processing Letters. Vol. 12. pp. 5–8.
↑ Symvonis, Antonios (1995). "इष्टतम स्थिर विलय". The Computer Journal. 38 (8): 681–690. CiteSeerX 10.1.1.55.6058. doi:10.1093/comjnl/38.8.681.
↑ Arne Kutzner. "इन-प्लेस मर्जिंग एल्गोरिथम बेंचमार्किंग टूल". Archived from the original on 2014-04-15. Retrieved 2014-03-23.
↑ Arne Kutzner. "इन-प्लेस मर्जिंग एल्गोरिथम बेंचमार्किंग टूल". Archived from the original on 2016-12-20. Retrieved 2016-12-11.
↑ "C, C++ और Java के लिए ब्लॉक सॉर्ट का सार्वजनिक डोमेन कार्यान्वयन". GitHub. Retrieved 2014-03-23.
↑ Tim Peters. "Re: WikiSort". Retrieved 2020-09-13.

[kim2008-1] 1.0 ^1.1 Kutzner, Arne; Kim, Pok-Son (2008). अनुपात आधारित स्थिर इन-प्लेस विलय (PDF). Lecture Notes in Computer Science. Vol. 4978. Springer Berlin Heidelberg. pp. 246–257. Retrieved 2016-09-07.

[mannilla-2] Mannila, Heikki; Ukkonen, Esko (14 May 1984). "इन-सीटू विलय के लिए एक सरल रैखिक समय एल्गोरिदम". Information Processing Letters. 18 (4): 203–208. doi:10.1016/0020-0190(84)90112-1.

[kronrod-3] Kronrod, M. Alexander (February 1969). "Оптимальный алгоритм упорядочения без рабочего поля" [An Optimal Ordering Algorithm without a Field of Operation]. Proceedings of the USSR Academy of Sciences (in русский). 186 (6): 1256–1258.

[4] Bentley, Jon (2006). प्रोग्रामिंग मोती (2nd ed.).

[Warren_2013-5] Warren Jr., Henry S. (2013) [2002]. हैकर की प्रसन्नता (2 ed.). Addison Wesley - Pearson Education, Inc. ISBN 978-0-321-84268-8. 0-321-84268-5.

[pardo-6] Pardo, Luis Trabb (1977). इष्टतम स्थान और समय सीमा के साथ स्थिर छँटाई और विलय. SIAM Journal on Computing. Vol. 6. pp. 351–372.

[geffert-7] 7.0 ^7.1 Geffert, Viliam; Katajainen, Jykri; Pasanen, Tomi (April 2000). "असम्बद्ध रूप से कुशल इन-प्लेस विलय". Theoretical Computer Science. 237 (1–2): 159–181. CiteSeerX 10.1.1.22.5750. doi:10.1016/S0304-3975(98)00162-5.

[8] Hwang, F. K.; Lin, S. (1972). दो असंयुक्त रैखिक क्रमित सेटों को मर्ज करने के लिए एक सरल एल्गोरिदम. SIAM Journal on Computing. Vol. 1. pp. 31–39. doi:10.1137/0201004. ISSN 0097-5397.

[dydek-9] Dudzinski, Krzysztof; Dydek, Andrzej (1981). एक स्थिर भंडारण विलय एल्गोरिदम पर. Information Processing Letters. Vol. 12. pp. 5–8.

[symvonis-10] Symvonis, Antonios (1995). "इष्टतम स्थिर विलय". The Computer Journal. 38 (8): 681–690. CiteSeerX 10.1.1.55.6058. doi:10.1093/comjnl/38.8.681.

[implementation-11] Arne Kutzner. "इन-प्लेस मर्जिंग एल्गोरिथम बेंचमार्किंग टूल". Archived from the original on 2014-04-15. Retrieved 2014-03-23.

[download-12] Arne Kutzner. "इन-प्लेस मर्जिंग एल्गोरिथम बेंचमार्किंग टूल". Archived from the original on 2016-12-20. Retrieved 2016-12-11.

[wikisort-13] "C, C++ और Java के लिए ब्लॉक सॉर्ट का सार्वजनिक डोमेन कार्यान्वयन". GitHub. Retrieved 2014-03-23.

[tim-14] Tim Peters. "Re: WikiSort". Retrieved 2020-09-13.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

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

Anonymous

Search

ब्लॉक सॉर्ट

Namespaces

More

Page actions

Contents

सिंहावलोकन

एल्गोरिथम

बाहरी लूप

बफ़र्स निकालें

टैग ए ब्लॉक

लुढ़कना और गिराना

स्थानीय विलय

पुनर्वितरित

वेरिएंट

विश्लेषण

जटिलता

मेमोरी

स्थिरता

अनुकूलता

लाभ

नुकसान

संदर्भ

Navigation

Navigation

Wiki tools

Wiki tools

Anonymous

Search

ब्लॉक सॉर्ट

सिंहावलोकन

एल्गोरिथम

बाहरी लूप

बफ़र्स निकालें

टैग ए ब्लॉक

लुढ़कना और गिराना

स्थानीय विलय

पुनर्वितरित

वेरिएंट

विश्लेषण

जटिलता

मेमोरी

स्थिरता

अनुकूलता

लाभ

नुकसान

संदर्भ

Navigation

Wiki tools

Page tools

Other projects

Categories