ब्लॉक सॉर्ट

Not to be confused with Block-sorting compression.

ब्लॉक सॉर्ट

File:Block sort with numbers 1 to 16 (thumb).gif ब्लॉक सॉर्ट स्थिर रूप से संख्याओं 1 से 16 तक सॉर्ट करें। 16 के समूहों को सम्मिलित करें, दो आंतरिक बफ़र्स निकालें, A ब्लॉक को टैग करें (आकार का √16 = 4 प्रत्येक), A ब्लॉक को B के माध्यम से रोल करें, उन्हें स्थानीय रूप से मर्ज करें, दूसरे बफ़र को सॉर्ट करें, और बफ़र्स को फिर से वितरित करें।
Class	सोर्टिंग एल्गोरिदम
Data structure	सरणी
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 में पोक-सोन किम और अर्ने कुट्ज़नर द्वारा स्थान मर्ज में O(log n) के लिए व्यावहारिक एल्गोरिदम प्रस्तावित किया गया था।

अवलोकन

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

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

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

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

एल्गोरिथम

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

|	bitwise OR
>>	shift right
%	modulo
++ and +=	increment
[x, y)	range से ≥ x और < y
|range|	range.end – range.start
array[i]	i-सरणी की वस्तु

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

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

 Rotate(array, amount, range)

    Reverse(array, range)
    Reverse(array, [range.start, range.start + amount))
    Reverse(array, [range.start + amount, range.end))

• दो की फलक घात: दो की अगली घात के लिए एक मान फलक करें। इस प्रकार 63 32 हो जाता है, 64 64 ही रहता है, इत्यादि।

FloorPowerOfTwo(x)
    x = x | (x >> 1)

    x = x | (x >> 2)
    x = x | (x >> 4)
    x = x | (x >> 8)
    x = x | (x >> 16)

    if (this isa  64-bit system)

        x = x | (x >> 32)
    return x - (x >> 1)

बाह्य पाश

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

   BlockSort(array)

       power_of_two = FloorPowerOfTwo(array.size)

       scale = array.size/power_of_two // 1.0 ≤ scale <2.0
      
       // insertion sort 16–31 items at a time

       for (merge = 0; merge < power_of_two; merge += 16)
           start = merge * scale
           end = start + 16 * scale
           InsertionSort(array, [start, end))
      
       for (length = 16; length < power_of_two; length += length)
           for (merge = 0; merge < power_of_two; merge += length * 2)
               start = merge * scale
               mid = (merge + length) * scale
               end = (merge + length * 2) * scale
              
               if (array[end − 1] < array[start])
                   // the two ranges are in reverse order, so a rotation is enough to merge them
                   Rotate(array, mid − start, [start, end))
               else if (array[mid − 1] > array[mid])
                   Merge(array, A = [start, mid), B = [mid, end))
               // else the ranges are already correctly ordered

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

   power_of_two = FloorPowerOfTwo(array.size)

   denominator = power_of_two/16
   numerator_step = array.size % denominator
   integer_step = floor(array.size/denominator)
  
   // insertion sort 16–31 items at a time
  
   while (integer_step < array.size)
       integer_part = numerator = 0
       while (integer_part < array.size)
           // get the ranges for A and B
           start = integer_part
          
           integer_part += integer_step
           numerator += numerator_step
           if (numerator ≥ denominator)
               numerator −= denominator
               integer_part++
          
           mid = integer_part
          
           integer_part += integer_step
           numerator += numerator_step
           if (numerator ≥ denominator)
               numerator −= denominator
               integer_part++
          
           end = integer_part
          
           if (array[end − 1] < array[start])
               Rotate(array, mid − start, [start, end))
           else if (array[mid − 1] > array[mid])
               Merge(array, A = [start, mid), B = [mid, end))
      
       integer_step += integer_step
       numerator_step += numerator_step
       if (numerator_step ≥ denominator)
           numerator_step −= denominator
           integer_step++

बफ़र निष्कर्ष

File:Buffer extraction for block sort.gif

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

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

while (integer_step < array.size)
    block_size = √integer_step

    buffer_size = integer_step/block_size + 1
    [extract two buffers of size 'buffer_size' each]

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

buffer_size = [number of unique values found]

block_size = integer_step/buffer_size + 1
  
integer_part = numerator = 0

while (integer_part < array.size)
    [get the ranges for A and B]
    [adjust A and B to not include the ranges used by the buffers]

टैग A ब्लॉक

File:Block sort tagging A blocks.gif

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

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

// blockA is the range of the remaining A blocks,
// and firstA is the unevenly sized first A block
blockA = [A.start, A.end)

firstA = [A.start, A.start + |blockA| % block_size)
  
// swap the second value of each A block with the value in buffer1

for (index = 0, indexA = firstA.end + 1; indexA < blockA.end; indexA += block_size)
    Swap(array[buffer1.start + index], array[indexA])

    index++
  
lastA = firstA

blockB = [B.start, B.start + minimum(block_size, |B|))
blockA.start += |firstA|

रोल और ड्राप

File:Block sort roll and drop.gif

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

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

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

   minA = blockA.start

   indexA = 0
  
   while (true)

       // if there's a previous B block and the first value of the minimum A block is ≤
       // the last value of the previous B block, then drop that minimum A block behind.
       // or if there are no B blocks left then keep dropping the remaining A blocks.
       if ((|lastB| > 0 and array[lastB.end - 1] ≥ array[minA]) or |blockB| = 0)
           // figure out where to split the previous B block, and rotate it at the split
           B_split = BinaryFirst(array, array[minA], lastB)

           B_remaining = lastB.end - B_split
          
           // swap the minimum A block to the beginning of the rolling A blocks

           BlockSwap(array, blockA.start, minA, block_size)
          
           // restore the second value for the A block

           Swap(array[blockA.start + 1], array[buffer1.start + indexA])
           indexA++
          
           // rotate the A block into the previous B block
           Rotate(array, blockA.start - B_split, [B_split, blockA.start + block_size))
          
           // locally merge the previous A block with the B values that follow it,
           // using the second internal buffer as swap space (if it exists)
           if (|buffer2| > 0)
               MergeInternal(array, lastA, [lastA.end, B_split), buffer2)
           else
               MergeInPlace(array, lastA, [lastA.end, B_split))
          
           // update the range for the remaining A blocks,
           // and the range remaining from the B block after it was split
           lastA = [blockA.start - B_remaining, blockA.start - B_remaining + block_size)
           lastB = [lastA.end, lastA.end + B_remaining)
          
           // if there are no more A blocks remaining, this step is finished
           blockA.start = blockA.start + block_size
           if (|blockA| = 0)
               break
          
           minA = [new minimum A block] (see below)
       else if (|blockB| < block_size)
           // move the last B block, which is unevenly sized,
           // to before the remaining A blocks, by using a rotation
           Rotate(array, blockB.start - blockA.start, [blockA.start, blockB.end))
          
           lastB = [blockA.start, blockA.start + |blockB|)
           blockA.start += |blockB|
           blockA.end += |blockB|
           minA += |blockB|
           blockB.end = blockB.start
       else
           // roll the leftmost A block to the end by swapping it with the next B block
           BlockSwap(array, blockA.start, blockB.start, block_size)
           lastB = [blockA.start, blockA.start + block_size)
           if (minA = blockA.start)
               minA = blockA.end
          
           blockA.start += block_size
           blockA.end += block_size
           blockB.start += block_size
          
           // this is equivalent to minimum(blockB.end + block_size, B.end),
           // but that has the potential to overflow
           if (blockB.end > B.end - block_size)
               blockB.end = B.end
           else
               blockB.end += block_size
  
   // merge the last A block with the remaining B values
   if (|buffer2| > 0)
       MergeInternal(array, lastA, [lastA.end, B.end), buffer2)
   else
       MergeInPlace(array, lastA, [lastA.end, B.end))

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

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

स्थानीय मर्ज

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

MergeInternal(array, A, B, buffer)
    // block swap the values in A with those in 'buffer'
    BlockSwap(array, A.start, buffer.start, |A|)

    A_count = 0, B_count = 0, insert = 0
    while (A_count < |A| and B_count < |B|)
        if (array[buffer.start + A_count] ≤ array[B.start + B_count])
            Swap(array[A.start + insert], array[buffer.start + A_count])
            A_count++

        else
            Swap(array[A.start + insert], array[B.start + B_count])

            B_count++
        insert++

    // block swap the remaining part of the buffer with the remaining part of the array
    BlockSwap(array, buffer.start + A_count, A.start + insert, |A| - A_count)

यदि दूसरा बफ़र स्थित नहीं है, तो द्रढ़ता से इन-प्लेस मर्ज संचालन किया जाना चाहिए, जैसे कि ह्वांग और लिन एल्गोरिदम का घूर्णन-आधारित संस्करण, डुडज़िंस्की और डायडेक एल्गोरिदम, या बार-बार बाइनरी खोज और घूर्णन।

MergeInPlace(array, A, B)
    while (|A| > 0 and |B| > 0)
        // find the first place in B where the first item in A needs to be inserted

        mid = BinaryFirst(array, array[A.start], B)

        // rotate A into place

        amount = mid - A.end
        Rotate(array, amount, [A.start, mid))

        // calculate the new A and B ranges
        B = [mid, B.end)
        A = [A.start + amount, mid)
        A.start = BinaryLast(array, array[A.start], A)

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

minA = blockA.start
for (findA = minA + block_size; findA < blockA.end - 1; findA += block_size)

    if (array[findA + 1] < array[minA + 1])
        minA = findA

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

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

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

पुनर्वितरित

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

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

प्रकार

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

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

बफ़र आकार के लिए ठीक विकल्पों में सम्मिलित हैं:

आकार	टिप्पणियाँ
(count + 1)/2	एक पूर्ण-गति मर्ज सॉर्ट में बदल जाता है क्योंकि सभी A उपसरणी इसमें फिट होंगी
√(count + 1)/2 + 1	यह मर्ज के सबसे बड़े स्तर पर A ब्लॉक का आकार होगा, इसलिए ब्लॉक सॉर्ट किसी भी वस्तु के लिए आंतरिक या इन-प्लेस मर्ज का उपयोग करना छोड़ सकता है
512	मर्ज सॉर्ट के छोटे स्तरों पर कई मर्जों को संभालने के लिए एक निश्चित आकार का बफर पर्याप्त है
0	यदि प्रणाली कोई अतिरिक्त मेमोरी आवंटित नहीं कर सकता है, तो कोई भी मेमोरी ठीक रूप से कार्य नहीं करती है

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

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

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

विश्लेषण

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

जटिलता

Further information: बड़े O संकेतन § सामान्य फलनों के क्रम

ब्लॉक सॉर्ट के प्रारंभ सरणी में 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)$ में समाप्त होता है।

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

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

ए ब्लॉक को टैग करने का कार्य किया जाता है ${\sqrt {A}}$ प्रत्येक A उपसरणी के लिए कई बार, फिर A ब्लॉक को रोल किया जाता है और B ब्लॉक में डाला जाता है ${\sqrt {A}}$ बार. स्थानीय मर्ज वही रहते हैं $O(n)$ मानक मर्ज की जटिलता, यद्यपि अधिक असाइनमेंट के साथ, क्योंकि मानों को कॉपी करने के अतिरिक्त स्वैप किया जाना चाहिए। नए न्यूनतम A ब्लॉक को खोजने के लिए रैखिक खोज पुनरावृत्त होती है ${\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) स्थान को सरल बनाता है जिसे संभवतः आवंटित किया जा सकता है।

स्थिरता

Further information: Sorting algorithm § Stability

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

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

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

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

अनुकूलता

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

लाभ

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

नुकसान

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