पॉलीफ़ेज़ मर्ज सॉर्ट: Difference between revisions

Revision as of 18:13, 15 July 2023

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

साधारण मर्ज सॉर्ट

मर्ज सॉर्ट एक डेटासेट के रिकॉर्ड को रिकॉर्ड के क्रमबद्ध रन में विभाजित करता है और फिर बार-बार सॉर्ट किए गए रन को बड़े क्रमबद्ध रन में मर्ज करता है जब तक कि केवल एक रन, सॉर्ट किया गया डेटासेट नहीं रह जाता है।

चार कार्यशील फ़ाइलों का उपयोग करके एक सामान्य मर्ज सॉर्ट उन्हें इनपुट फ़ाइलों की एक जोड़ी और आउटपुट फ़ाइलों की एक जोड़ी के रूप में व्यवस्थित करता है। डेटासेट को दो कार्यशील फ़ाइलों के बीच समान रूप से वितरित किया जाता है, या तो क्रमबद्ध रन के रूप में या सरलतम मामले में, एकल रिकॉर्ड, जिसे आकार 1 के क्रमबद्ध रन माना जा सकता है। एक बार जब सभी डेटासेट दो कार्यशील फ़ाइलों में स्थानांतरित हो जाते हैं, तो वे दो कार्यशील फ़ाइलें पहले मर्ज पुनरावृत्ति के लिए इनपुट फ़ाइलें बन जाती हैं। प्रत्येक मर्ज पुनरावृत्ति मर्ज दो इनपुट कार्यशील फ़ाइलों से चलती है, दो आउटपुट फ़ाइलों के बीच मर्ज किए गए आउटपुट को वैकल्पिक करती है, फिर से मर्ज किए गए रन को दो आउटपुट फ़ाइलों के बीच समान रूप से वितरित करती है (अंतिम मर्ज पुनरावृत्ति तक)। एक बार जब दो इनपुट फ़ाइलों से सभी रन विलय और आउटपुट हो जाते हैं, तो आउटपुट फ़ाइलें इनपुट फ़ाइलें बन जाती हैं और अगले मर्ज पुनरावृत्ति के लिए जो इसके विपरीत भी संभव है। प्रत्येक पुनरावृत्ति पर रन की संख्या 2 के कारक से घट जाती है, जैसे कि 64, 32, 16, 8, 4, 2, 1। अंतिम मर्ज पुनरावृत्ति के लिए, दो इनपुट फ़ाइलों में केवल एक क्रमबद्ध रन (1/2) होता है डेटासेट) प्रत्येक, और मर्ज किया गया परिणाम आउटपुट फ़ाइलों में से एक पर एकल सॉर्ट किया गया रन (सॉर्ट किया गया डेटासेट) है। इसका वर्णन मर्ज सॉर्ट § टेप ड्राइव के साथ उपयोग में भी किया गया है।

यदि केवल तीन कार्यशील फ़ाइलें हैं, तो एक साधारण मर्ज सॉर्ट दो कार्यशील फ़ाइलों से सॉर्ट किए गए रन को एक कार्यशील फ़ाइल में मर्ज कर देता है, फिर रन को दो आउटपुट फ़ाइलों के बीच समान रूप से वितरित करता है। मर्ज पुनरावृत्ति रन संख्या को 2 के कारक से कम कर देता है, पुनर्वितरित पुनरावृत्ति रन गणना को कम नहीं करता है (कारक 1 है)। प्रत्येक पुनरावृत्ति को √2 ≈ 1.41 के औसत कारक द्वारा रन गिनती को कम करने पर विचार किया जा सकता है। यदि 5 कार्यशील फ़ाइलें हैं, तो पैटर्न √6 ≈ 2.45 के औसत कारक के लिए, 3-तरफा मर्ज और 2-तरफा मर्ज के बीच वैकल्पिक होता है।

सामान्यतः, कार्यशील फ़ाइलों की सम संख्या N के लिए, सामान्य मर्ज सॉर्ट का प्रत्येक पुनरावृत्ति रन संख्या को N/2 के कारक से कम कर देता है, जबकि कार्यशील फ़ाइलों की विषम संख्या N के लिए, प्रत्येक पुनरावृत्ति रन संख्या को √(N²−1)/4 = √N²−1/2 के औसत कारक से कम कर देता है।

पॉलीफ़ेज़ मर्ज

N <8 कार्यशील फ़ाइलों के लिए, एक पॉलीफ़ेज़ मर्ज सॉर्ट N−1 कार्यशील फ़ाइलों के बीच क्रमबद्ध रन को असमान रूप से वितरित करके एक उच्च प्रभावी रन गिनती कमी कारक प्राप्त करता है (अगले भाग में समझाया गया है)। प्रत्येक पुनरावृत्ति विलय N−1 कार्यशील फ़ाइलों से एकल आउटपुट कार्यशील फ़ाइल पर चलता है। जब N−1 कार्यशील फ़ाइलों में से एक का अंत पहुँच जाता है, तो यह नई आउटपुट फ़ाइल बन जाती है और जो आउटपुट फ़ाइल थी वह N−1 कार्यशील इनपुट फ़ाइलों में से एक बन जाती है, जिससे पॉलीफ़ेज़ मर्ज सॉर्ट का एक नया पुनरावृत्ति शुरू हो जाता है। प्रत्येक पुनरावृत्ति डेटासेट के केवल एक अंश (प्राय 1/2 से 3/4) को मर्ज करती है, अंतिम पुनरावृत्ति को छोड़कर जो सभी डेटासेट को एक ही क्रमबद्ध रन में मर्ज कर देता है। प्रारंभिक वितरण स्थापित किया गया है जिससे कि एक समय में केवल एक इनपुट वर्किंग फ़ाइल खाली हो, अंतिम मर्ज पुनरावृत्ति को छोड़कर जो N−1 इनपुट वर्किंग फ़ाइलों से N−1 सिंगल रन (अलग-अलग आकार के, इसे आगे समझाया गया है) को मर्ज करता है। एकल आउटपुट फ़ाइल में, जिसके परिणामस्वरूप एकल क्रमबद्ध रन, क्रमबद्ध डेटासेट होता है।

प्रत्येक पॉलीफ़ेज़ पुनरावृत्ति के लिए, रनों की कुल संख्या उच्च क्रम अनुक्रम के उलट फाइबोनैचि संख्याओं के समान एक पैटर्न का अनुसरण करती है। 4 फ़ाइलों और 57 रन वाले डेटासेट के साथ, प्रत्येक पुनरावृत्ति पर कुल रन संख्या 57, 31, 17, 9, 5, 3, 1 होगी।^[1]^[2] ध्यान दें कि अंतिम पुनरावृत्ति को छोड़कर, रन गिनती में कमी कारक 2, 57/31, 31/17, 17/9, 9/5, 5/3, 3/1 से थोड़ा कम है, 4 फ़ाइल के लिए प्राय 1.84 मामला, लेकिन अंतिम को छोड़कर प्रत्येक पुनरावृत्ति ने प्राय 65% डेटासेट को संसाधित करते समय रन गिनती को कम कर दिया, इसलिए मध्यवर्ती पुनरावृत्तियों के समय संसाधित प्रति डेटासेट रन गिनती में कमी कारक प्राय 1.84 / 0.65 = 2.83 है। प्रत्येक 1 रिकॉर्ड के 57 रन वाले डेटासेट के लिए, प्रारंभिक वितरण के पश्चात, पॉलीफ़ेज़ मर्ज सॉर्ट 2.70 के समग्र कमी कारक के लिए डेटासेट को सॉर्ट करने के लिए लगने वाले 6 पुनरावृत्तियों के समय 232 रिकॉर्ड ले जाता है (इसे पश्चात में अधिक विस्तार से समझाया गया है)

पहले पॉलीफ़ेज़ पुनरावृत्ति के पश्चात, आउटपुट फ़ाइल में अब N−1 मूल रन के विलय के परिणाम सम्मलित हैं, लेकिन शेष N−2 इनपुट कार्यशील फ़ाइलों में अभी भी शेष मूल रन सम्मलित हैं, इसलिए दूसरा मर्ज पुनरावृत्ति आकार के रन उत्पन्न करता है (N−1) + (N−2) = (2N − 3) मूल रन। तीसरा पुनरावृत्ति आकार (4N − 7) के मूल रन उत्पन्न करता है। 4 फ़ाइलों के साथ, पहला पुनरावृत्ति आकार 3 मूल रन बनाता है, दूसरा पुनरावृत्ति 5 मूल रन बनाता है, तीसरा पुनरावृत्ति 9 मूल रन बनाता है और इसी तरह, फाइबोनैचि जैसे पैटर्न का अनुसरण करते हुए, 1, 3, 5, 9, 17, 31, 57, ..., इसलिए रन आकार में वृद्धि उसी पैटर्न का अनुसरण करती है, जिसके विपरीत रन संख्या में कमी होती है। 4 फ़ाइलों और 1 रिकॉर्ड के 57 रन के उदाहरण मामले में, अंतिम पुनरावृत्ति 31, 17, 9 आकार के 3 रन को मर्ज करती है, जिसके परिणामस्वरूप आकार 31+17+9 = 57 रिकॉर्ड का एकल क्रमबद्ध रन होता है, क्रमबद्ध डेटासेट। 4 फ़ाइलों, 31 रिकॉर्ड के लिए रन गणना और रन आकार का एक उदाहरण तालिका 4.3 में पाया जा सकता है।^[3]

परफेक्ट 3 फ़ाइल पॉलीफ़ेज़ मर्ज सॉर्ट

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

फ़ाइल 1 अभी-अभी खाली हुई और नई आउटपुट फ़ाइल बन गई। प्रत्येक इनपुट टेप पर एक रन छोड़ा गया है, और उन रन को एक साथ मर्ज करने से सॉर्ट की गई फ़ाइल बन जाएगी।

File 1 (out):                                           <1 run> *        (the sorted file)
File 2 (in ): ... | <1 run> *               -->     ... <1 run> | *          (consumed)
File 3 (in ):     | <1 run> *                           <1 run> | *          (consumed)

...  possible runs that have already been read
|    marks the read pointer of the file
*    marks end of file

पिछले पुनरावृत्ति पर वापस लौटते हुए, हम 1 और 2 से पढ़ रहे थे। फ़ाइल 1 खाली होने से पहले 1 और 2 से एक रन मर्ज किया जाता है। ध्यान दें कि फ़ाइल 2 पूरी तरह से ख़त्म नहीं हुई है—अंतिम मर्ज (ऊपर) से मेल खाने के लिए इसमें एक रन बचा है।

File 1 (in ): ... | <1 run> *                      ... <1 run> | *
File 2 (in ):     | <2 run> *           -->            <1 run> | <1 run> *
File 3 (out):                                          <1 run> *

एक और पुनरावृत्ति को पीछे छोड़ते हुए, फ़ाइल 3 के खाली होने से पहले 1 और 3 से 2 रन मर्ज किए जाते हैं।

File 1 (in ):     | <3 run>                        ... <2 run> | <1 run> *
File 2 (out):                               -->        <2 run> *
File 3 (in ): ... | <2 run> *                          <2 run> | *

एक और पुनरावृत्ति को पीछे छोड़ते हुए, फ़ाइल 2 के खाली होने से पहले 2 और 3 से 3 रन मर्ज कर दिए जाते हैं।

File 1 (out):                                          <3 run> *
File 2 (in ): ... | <3 run> *               -->    ... <3 run> | *
File 3 (in ):     | <5 run> *                          <3 run> | <2 run> *

एक और पुनरावृत्ति को पीछे छोड़ते हुए, फ़ाइल 1 के खाली होने से पहले 1 और 2 से 5 रन मर्ज कर दिए जाते हैं।

File 1 (in ): ... | <5 run> *                      ... <5 run> | *
File 2 (in ):     | <8 run> *               -->        <5 run> | <3 run> *
File 3 (out):                                          <5 run> *

पॉलीफ़ेज़ मर्ज सॉर्ट के लिए वितरण

सही 3 फ़ाइल केस को देखते हुए, मर्ज किए गए पीछे की ओर काम करने के लिए रनों की संख्या: 1, 1, 2, 3, 5, ... एक फाइबोनैचि अनुक्रम का पता चलता है। 3 से अधिक फ़ाइलों का क्रम थोड़ा अधिक जटिल है; 4 फ़ाइलों के लिए, अंतिम स्थिति से शुरू करके और पीछे की ओर काम करते हुए, रन गिनती पैटर्न {1,0,0,0}, {0,1,1,1}, {1,0,2,2}, {3 है ,2,0,4}, {7,6,4,0}, {0,13,11,7}, {13,0,24,20}, ...।

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

व्यवहार में, इनपुट फ़ाइल में पूर्ण वितरण के लिए आवश्यक रनों की सटीक संख्या नहीं होगी। इससे निपटने का एक तरीका एक आदर्श रन वितरण का अनुकरण करने के लिए काल्पनिक "डमी रन" के साथ वास्तविक वितरण को पैडिंग करना है।^[1] एक डमी रन एक ऐसे रन की तरह व्यवहार करता है जिसमें कोई रिकॉर्ड नहीं होता है। एक या अधिक डमी रन को एक या अधिक वास्तविक रन के साथ मर्ज करने से केवल वास्तविक रन ही मर्ज होते हैं, और बिना किसी वास्तविक रन के एक या अधिक डमी रन को मर्ज करने से एकल डमी रन बनता है। एक अन्य दृष्टिकोण मर्ज ऑपरेशन के समय आवश्यकतानुसार डमी रन का अनुकरण करना है।^[4]

"इष्टतम" वितरण एल्गोरिदम के लिए रनों की संख्या पहले से जानने की आवश्यकता होती है। अन्यथा, अधिक सामान्य मामले में जहां रनों की संख्या पहले से ज्ञात नहीं होती है, "इष्टतम के निकट" वितरण एल्गोरिदम का उपयोग किया जाता है। कुछ वितरण एल्गोरिदम में रन को पुनर्व्यवस्थित करना सम्मलित है।^[5] यदि रनों की संख्या पहले से ज्ञात है, तो मर्ज चरणों को शुरू करने से पहले केवल आंशिक वितरण की आवश्यकता होती है। उदाहरण के लिए, 3 फ़ाइल केस पर विचार करें, जो फ़ाइल_1 में n रन से शुरू होता है। F_i = F_i₋₁ + F_i−2 को iवें फाइबोनैचि संख्या के रूप में परिभाषित करें। यदि n = F_i, तो F_i₋₂ रन को File_2 पर ले जाएं, F_i₋₁ रन को File_1 पर शेष छोड़ दें, जो एक आदर्श रन वितरण है। यदि F_i < n < F_i₊₁, तो n−F_i को File_2 पर चलाएं और F_i₊₁−n को File_3 पर चलाएं। पहला मर्ज पुनरावृत्ति फ़ाइल_1 और फ़ाइल_2 से n−F_i रन को मर्ज करता है, n−F_i मर्ज किए गए रन को F_i₊₁−n रन में जोड़ता है जो पहले से ही File_3 में ले जाया गया है। File_1 Fi-2 रन शेष के साथ समाप्त होता है, File_2 खाली हो जाता है, और File_3 Fi−1 रन के साथ समाप्त होता है, फिर से एक आदर्श रन वितरण। 4 या अधिक फ़ाइलों के लिए, गणित अधिक जटिल है, लेकिन अवधारणा समान है।

तुलना बनाम साधारण मर्ज सॉर्ट

प्रारंभिक वितरण के पश्चात, 4 फ़ाइलों का उपयोग करके एक सामान्य मर्ज सॉर्ट पूरे डेटासेट के 4 पुनरावृत्तियों में 16 एकल रिकॉर्ड रन को सॉर्ट करेगा, प्रारंभिक वितरण के पश्चात डेटासेट को सॉर्ट करने के लिए कुल 64 रिकॉर्ड को स्थानांतरित करेगा। 4 फ़ाइलों का उपयोग करके एक पॉलीफ़ेज़ मर्ज सॉर्ट 4 पुनरावृत्तियों में 17 एकल रिकॉर्ड को सॉर्ट करेगा, लेकिन चूंकि प्रत्येक पुनरावृत्ति लेकिन अंतिम पुनरावृत्ति केवल डेटासेट के एक अंश को स्थानांतरित करती है, यह प्रारंभिक के पश्चात डेटासेट को सॉर्ट करने के लिए कुल 48 रिकॉर्ड को ही स्थानांतरित वितरण करती है। इस मामले में, सामान्य मर्ज सॉर्ट फ़ैक्टर 2.0 है, जबकि पॉलीफ़ेज़ समग्र फ़ैक्टर ≈2.73 है।

यह समझाने के लिए कि कमी कारक सॉर्ट प्रदर्शन से कैसे संबंधित है, कमी कारक समीकरण हैं:

reduction_factor = exp(number_of_runs*log(number_of_runs)/run_move_count)
run_move_count = number_of_runs * log(number_of_runs)/log(reduction_factor)
run_move_count = number_of_runs * log_reduction_factor(number_of_runs)

उपरोक्त उदाहरणों के लिए रन मूव काउंट समीकरण का उपयोग करना:

साधारण मर्ज सॉर्ट → $16\times \log _{2}(16)=64$ ,
पॉलीफ़ेज़ मर्ज सॉर्ट → $17\times \log _{2.73}(17)=48$ .

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

# files
|     average fraction of data per iteration
|     |     polyphase reduction factor on ideal sized data
|     |     |     ordinary reduction factor on ideal sized data
|     |     |     |
3     .73   1.94  1.41  (sqrt  2)
4     .63   2.68  2.00
5     .58   3.20  2.45  (sqrt  6)
6     .56   3.56  3.00
7     .55   3.80  3.46  (sqrt 12)
8     .54   3.95  4.00
9     .53   4.07  4.47  (sqrt 20)
10    .53   4.15  5.00
11    .53   4.22  5.48  (sqrt 30)
12    .53   4.28  6.00
32    .53   4.87 16.00

सामान्यतः, जब 8 से कम फ़ाइलें होती हैं तो पॉलीफ़ेज़ मर्ज सॉर्ट सामान्य मर्ज सॉर्ट से बेहतर होता है, जबकि सामान्य मर्ज सॉर्ट प्राय 8 या अधिक फ़ाइलों पर बेहतर होने लगता है।^[6]^[7]

संदर्भ

↑ ^1.0 ^1.1 Donald Knuth, The Art of Computer Programming, Volume 3, Addison Wesley, 1973, Algorithm 5.4.2D.
↑ "एल्गोरिदम को सॉर्ट करना और खोजना". Archived from the original on 2012-11-22. Retrieved 2010-01-31.
↑ "बाहरी छँटाई". Archived from the original on 2016-01-28. Retrieved 2016-01-22.
↑ https://www.fq.math.ca/Scanned/8-1/lynch.pdf^{[bare URL PDF]}
↑ http://i.stanford.edu/pub/cstr/reports/cs/tr/76/543/CS-TR-76-543.pdf^{[bare URL PDF]}
↑ "Advanced Programming I Lecture Notes".
↑ http://www.mif.vu.lt/~algis/dsax/DsSort.pdf^{[bare URL PDF]}

अग्रिम पठन

ब्राडली, जेम्स (1982), फ़ाइल और डेटा बेस तकनीकें, होल्ट, राइनहार्ट और विंस्टन, ISBN 0-03-058673-9 {{citation}}: Invalid |url-access=पंजीकरण (help)
रेनॉल्ड्स, सैमुअल डब्ल्यू. (अगस्त 1961), "एक सामान्यीकृत पॉलीफ़ेज़ मर्ज एल्गोरिदम", एसीएम का संचार, न्यूयॉर्क, एनवाई: एसीएम, 4 (8): 347–349, doi:10.1145/366678.366689, S2CID 28416100 {{citation}}: Check date values in: |date= (help)
सेडगेविक, रॉबर्ट (1983), एल्गोरिदम, एडिसन-वेस्ले, pp. 163–165, ISBN 0-201-06672-6 {{citation}}: Invalid |url-access=पंजीकरण (help)

बाहरी संबंध

[Knuth1973-1] 1.0 ^1.1 Donald Knuth, The Art of Computer Programming, Volume 3, Addison Wesley, 1973, Algorithm 5.4.2D.

[2] "एल्गोरिदम को सॉर्ट करना और खोजना". Archived from the original on 2012-11-22. Retrieved 2010-01-31.

[3] "बाहरी छँटाई". Archived from the original on 2016-01-28. Retrieved 2016-01-22.

[4] ttps://www.fq.math.ca/Scanned/8-1/lynch.pdf^{[bare URL PDF]}

[5] ttp://i.stanford.edu/pub/cstr/reports/cs/tr/76/543/CS-TR-76-543.pdf^{[bare URL PDF]}

[6] "Advanced Programming I Lecture Notes".

[7] ttp://www.mif.vu.lt/~algis/dsax/DsSort.pdf^{[bare URL PDF]}

[1]

[2]

[3]

[4]

[5]

[6]

[7]

@@ Line 11: / Line 11: @@
 यदि केवल तीन कार्यशील फ़ाइलें हैं, तो एक साधारण मर्ज सॉर्ट दो कार्यशील फ़ाइलों से सॉर्ट किए गए रन को एक कार्यशील फ़ाइल में मर्ज कर देता है, फिर रन को दो आउटपुट फ़ाइलों के बीच समान रूप से वितरित करता है। मर्ज पुनरावृत्ति रन संख्या को 2 के कारक से कम कर देता है, पुनर्वितरित पुनरावृत्ति रन गणना को कम नहीं करता है (कारक 1 है)। प्रत्येक पुनरावृत्ति को {{sqrt|2}} ≈ 1.41 के औसत कारक द्वारा रन गिनती को कम करने पर विचार किया जा सकता है। यदि 5 कार्यशील फ़ाइलें हैं, तो पैटर्न  {{sqrt|6}} ≈ 2.45 के औसत कारक के लिए, 3-तरफा मर्ज और 2-तरफा मर्ज के बीच वैकल्पिक होता है।
-सामान्य तौर पर, कार्यशील फ़ाइलों की सम संख्या N के लिए, सामान्य मर्ज सॉर्ट का प्रत्येक पुनरावृत्ति रन संख्या को N/2 के कारक से कम कर देता है, जबकि कार्यशील फ़ाइलों की विषम संख्या N के लिए, प्रत्येक पुनरावृत्ति रन संख्या को  {{sqrt|(''N''<sup>2</sup>−1)/4}} = {{sqrt|''N''<sup>2</sup>−1}}/2 के औसत कारक से कम कर देता है।
+सामान्यतः, कार्यशील फ़ाइलों की सम संख्या N के लिए, सामान्य मर्ज सॉर्ट का प्रत्येक पुनरावृत्ति रन संख्या को N/2 के कारक से कम कर देता है, जबकि कार्यशील फ़ाइलों की विषम संख्या N के लिए, प्रत्येक पुनरावृत्ति रन संख्या को  {{sqrt|(''N''<sup>2</sup>−1)/4}} = {{sqrt|''N''<sup>2</sup>−1}}/2 के औसत कारक से कम कर देता है।
 ==पॉलीफ़ेज़ मर्ज==
-N <8 कार्यशील फ़ाइलों के लिए, एक पॉलीफ़ेज़ मर्ज सॉर्ट N−1 कार्यशील फ़ाइलों के बीच क्रमबद्ध रन को असमान रूप से वितरित करके एक उच्च प्रभावी रन गिनती कमी कारक प्राप्त करता है (अगले भाग में समझाया गया है)। प्रत्येक पुनरावृत्ति विलय N−1 कार्यशील फ़ाइलों से एकल आउटपुट कार्यशील फ़ाइल पर चलता है। जब N−1 कार्यशील फ़ाइलों में से एक का अंत पहुँच जाता है, तो यह नई आउटपुट फ़ाइल बन जाती है और जो आउटपुट फ़ाइल थी वह N−1 कार्यशील इनपुट फ़ाइलों में से एक बन जाती है, जिससे पॉलीफ़ेज़ मर्ज सॉर्ट का एक नया पुनरावृत्ति शुरू हो जाता है। प्रत्येक पुनरावृत्ति डेटासेट के केवल एक अंश (लगभग 1/2 से 3/4) को मर्ज करती है, अंतिम पुनरावृत्ति को छोड़कर जो सभी डेटासेट को एक ही क्रमबद्ध रन में मर्ज कर देता है। प्रारंभिक वितरण स्थापित किया गया है ताकि एक समय में केवल एक इनपुट वर्किंग फ़ाइल खाली हो, अंतिम मर्ज पुनरावृत्ति को छोड़कर जो N−1 इनपुट वर्किंग फ़ाइलों से N−1 सिंगल रन (अलग-अलग आकार के, इसे आगे समझाया गया है) को मर्ज करता है। एकल आउटपुट फ़ाइल में, जिसके परिणामस्वरूप एकल क्रमबद्ध रन, क्रमबद्ध डेटासेट होता है।
+N <8 कार्यशील फ़ाइलों के लिए, एक पॉलीफ़ेज़ मर्ज सॉर्ट N−1 कार्यशील फ़ाइलों के बीच क्रमबद्ध रन को असमान रूप से वितरित करके एक उच्च प्रभावी रन गिनती कमी कारक प्राप्त करता है (अगले भाग में समझाया गया है)। प्रत्येक पुनरावृत्ति विलय N−1 कार्यशील फ़ाइलों से एकल आउटपुट कार्यशील फ़ाइल पर चलता है। जब N−1 कार्यशील फ़ाइलों में से एक का अंत पहुँच जाता है, तो यह नई आउटपुट फ़ाइल बन जाती है और जो आउटपुट फ़ाइल थी वह N−1 कार्यशील इनपुट फ़ाइलों में से एक बन जाती है, जिससे पॉलीफ़ेज़ मर्ज सॉर्ट का एक नया पुनरावृत्ति शुरू हो जाता है। प्रत्येक पुनरावृत्ति डेटासेट के केवल एक अंश (प्राय 1/2 से 3/4) को मर्ज करती है, अंतिम पुनरावृत्ति को छोड़कर जो सभी डेटासेट को एक ही क्रमबद्ध रन में मर्ज कर देता है। प्रारंभिक वितरण स्थापित किया गया है जिससे कि एक समय में केवल एक इनपुट वर्किंग फ़ाइल खाली हो, अंतिम मर्ज पुनरावृत्ति को छोड़कर जो N−1 इनपुट वर्किंग फ़ाइलों से N−1 सिंगल रन (अलग-अलग आकार के, इसे आगे समझाया गया है) को मर्ज करता है। एकल आउटपुट फ़ाइल में, जिसके परिणामस्वरूप एकल क्रमबद्ध रन, क्रमबद्ध डेटासेट होता है।
-प्रत्येक पॉलीफ़ेज़ पुनरावृत्ति के लिए, रनों की कुल संख्या उच्च क्रम अनुक्रम के उलट फाइबोनैचि संख्याओं के समान एक पैटर्न का अनुसरण करती है। 4 फ़ाइलों और 57 रन वाले डेटासेट के साथ, प्रत्येक पुनरावृत्ति पर कुल रन संख्या 57, 31, 17, 9, 5, 3, 1 होगी।<ref name="Knuth1973">[[Donald Knuth]], [[The Art of Computer Programming]], Volume 3, Addison Wesley, 1973, Algorithm 5.4.2D.</ref><ref>{{Cite web |url=http://oopweb.com/Algorithms/Documents/Sman/Volume/ExternalSorting.html |title=एल्गोरिदम को सॉर्ट करना और खोजना|access-date=2010-01-31 |archive-url=https://web.archive.org/web/20121122215836/http://oopweb.com/Algorithms/Documents/Sman/Volume/ExternalSorting.html |archive-date=2012-11-22 |url-status=dead }}</ref> ध्यान दें कि अंतिम पुनरावृत्ति को छोड़कर, रन गिनती में कमी कारक 2, 57/31, 31/17, 17/9, 9/5, 5/3, 3/1 से थोड़ा कम है, 4 फ़ाइल के लिए लगभग 1.84 मामला, लेकिन अंतिम को छोड़कर प्रत्येक पुनरावृत्ति ने लगभग 65% डेटासेट को संसाधित करते समय रन गिनती को कम कर दिया, इसलिए मध्यवर्ती पुनरावृत्तियों के दौरान संसाधित प्रति डेटासेट रन गिनती में कमी कारक लगभग 1.84 / 0.65 = 2.83 है। प्रत्येक 1 रिकॉर्ड के 57 रन वाले डेटासेट के लिए, प्रारंभिक वितरण के बाद, पॉलीफ़ेज़ मर्ज सॉर्ट 2.70 के समग्र कमी कारक के लिए डेटासेट को सॉर्ट करने के लिए लगने वाले 6 पुनरावृत्तियों के दौरान 232 रिकॉर्ड ले जाता है (इसे बाद में अधिक विस्तार से समझाया गया है)
+प्रत्येक पॉलीफ़ेज़ पुनरावृत्ति के लिए, रनों की कुल संख्या उच्च क्रम अनुक्रम के उलट फाइबोनैचि संख्याओं के समान एक पैटर्न का अनुसरण करती है। 4 फ़ाइलों और 57 रन वाले डेटासेट के साथ, प्रत्येक पुनरावृत्ति पर कुल रन संख्या 57, 31, 17, 9, 5, 3, 1 होगी।<ref name="Knuth1973">[[Donald Knuth]], [[The Art of Computer Programming]], Volume 3, Addison Wesley, 1973, Algorithm 5.4.2D.</ref><ref>{{Cite web |url=http://oopweb.com/Algorithms/Documents/Sman/Volume/ExternalSorting.html |title=एल्गोरिदम को सॉर्ट करना और खोजना|access-date=2010-01-31 |archive-url=https://web.archive.org/web/20121122215836/http://oopweb.com/Algorithms/Documents/Sman/Volume/ExternalSorting.html |archive-date=2012-11-22 |url-status=dead }}</ref> ध्यान दें कि अंतिम पुनरावृत्ति को छोड़कर, रन गिनती में कमी कारक 2, 57/31, 31/17, 17/9, 9/5, 5/3, 3/1 से थोड़ा कम है, 4 फ़ाइल के लिए प्राय 1.84 मामला, लेकिन अंतिम को छोड़कर प्रत्येक पुनरावृत्ति ने प्राय 65% डेटासेट को संसाधित करते समय रन गिनती को कम कर दिया, इसलिए मध्यवर्ती पुनरावृत्तियों के समय संसाधित प्रति डेटासेट रन गिनती में कमी कारक प्राय 1.84 / 0.65 = 2.83 है। प्रत्येक 1 रिकॉर्ड के 57 रन वाले डेटासेट के लिए, प्रारंभिक वितरण के पश्चात, पॉलीफ़ेज़ मर्ज सॉर्ट 2.70 के समग्र कमी कारक के लिए डेटासेट को सॉर्ट करने के लिए लगने वाले 6 पुनरावृत्तियों के समय 232 रिकॉर्ड ले जाता है (इसे पश्चात में अधिक विस्तार से समझाया गया है)
-पहले पॉलीफ़ेज़ पुनरावृत्ति के बाद, आउटपुट फ़ाइल में अब N−1 मूल रन के विलय के परिणाम शामिल हैं, लेकिन शेष N−2 इनपुट कार्यशील फ़ाइलों में अभी भी शेष मूल रन शामिल हैं, इसलिए दूसरा मर्ज पुनरावृत्ति आकार के रन उत्पन्न करता है (''N''−1) + (''N''−2) = (2''N'' − 3)  मूल रन। तीसरा पुनरावृत्ति आकार (4''N'' − 7) के मूल रन उत्पन्न करता है। 4 फ़ाइलों के साथ, पहला पुनरावृत्ति आकार 3 मूल रन बनाता है, दूसरा पुनरावृत्ति 5 मूल रन बनाता है, तीसरा पुनरावृत्ति 9 मूल रन बनाता है और इसी तरह, फाइबोनैचि जैसे पैटर्न का अनुसरण करते हुए, 1, 3, 5, 9, 17, 31, 57, ..., इसलिए रन आकार में वृद्धि उसी पैटर्न का अनुसरण करती है, जिसके विपरीत रन संख्या में कमी होती है। 4 फ़ाइलों और 1 रिकॉर्ड के 57 रन के उदाहरण मामले में, अंतिम पुनरावृत्ति 31, 17, 9 आकार के 3 रन को मर्ज करती है, जिसके परिणामस्वरूप आकार 31+17+9 = 57 रिकॉर्ड का एकल क्रमबद्ध रन होता है, क्रमबद्ध डेटासेट। 4 फ़ाइलों, 31 रिकॉर्ड के लिए रन गणना और रन आकार का एक उदाहरण तालिका 4.3 में पाया जा सकता है।<ref>{{cite web |url=http://pluto.ksi.edu/~cyh/cis501/ch4.htm |title=बाहरी छँटाई|accessdate=2016-01-22 |url-status=dead |archiveurl=https://web.archive.org/web/20160128191110/http://pluto.ksi.edu/~cyh/cis501/ch4.htm |archivedate=2016-01-28 }}</ref>
+पहले पॉलीफ़ेज़ पुनरावृत्ति के पश्चात, आउटपुट फ़ाइल में अब N−1 मूल रन के विलय के परिणाम सम्मलित हैं, लेकिन शेष N−2 इनपुट कार्यशील फ़ाइलों में अभी भी शेष मूल रन सम्मलित हैं, इसलिए दूसरा मर्ज पुनरावृत्ति आकार के रन उत्पन्न करता है (''N''−1) + (''N''−2) = (2''N'' − 3)  मूल रन। तीसरा पुनरावृत्ति आकार (4''N'' − 7) के मूल रन उत्पन्न करता है। 4 फ़ाइलों के साथ, पहला पुनरावृत्ति आकार 3 मूल रन बनाता है, दूसरा पुनरावृत्ति 5 मूल रन बनाता है, तीसरा पुनरावृत्ति 9 मूल रन बनाता है और इसी तरह, फाइबोनैचि जैसे पैटर्न का अनुसरण करते हुए, 1, 3, 5, 9, 17, 31, 57, ..., इसलिए रन आकार में वृद्धि उसी पैटर्न का अनुसरण करती है, जिसके विपरीत रन संख्या में कमी होती है। 4 फ़ाइलों और 1 रिकॉर्ड के 57 रन के उदाहरण मामले में, अंतिम पुनरावृत्ति 31, 17, 9 आकार के 3 रन को मर्ज करती है, जिसके परिणामस्वरूप आकार 31+17+9 = 57 रिकॉर्ड का एकल क्रमबद्ध रन होता है, क्रमबद्ध डेटासेट। 4 फ़ाइलों, 31 रिकॉर्ड के लिए रन गणना और रन आकार का एक उदाहरण तालिका 4.3 में पाया जा सकता है।<ref>{{cite web |url=http://pluto.ksi.edu/~cyh/cis501/ch4.htm |title=बाहरी छँटाई|accessdate=2016-01-22 |url-status=dead |archiveurl=https://web.archive.org/web/20160128191110/http://pluto.ksi.edu/~cyh/cis501/ch4.htm |archivedate=2016-01-28 }}</ref>
 ==परफेक्ट 3 फ़ाइल पॉलीफ़ेज़ मर्ज सॉर्ट==
-पॉलीफ़ेज़ मर्ज को उसकी अंतिम स्थितियों से शुरू करके पीछे की ओर काम करते हुए देखना सबसे आसान है। प्रत्येक पुनरावृत्ति की शुरुआत में, दो इनपुट फ़ाइलें और एक आउटपुट फ़ाइल होगी। पुनरावृत्ति के अंत में, एक इनपुट फ़ाइल पूरी तरह से समाप्त हो जाएगी और अगले पुनरावृत्ति के लिए आउटपुट फ़ाइल बन जाएगी। वर्तमान आउटपुट फ़ाइल अगले पुनरावृत्ति के लिए एक इनपुट फ़ाइल बन जाएगी। शेष फ़ाइलें (3 फ़ाइल केस में केवल एक) केवल आंशिक रूप से उपभोग की गई हैं और उनके शेष रन अगले पुनरावृत्ति के लिए इनपुट होंगे।
+पॉलीफ़ेज़ मर्ज को उसकी अंतिम स्थितियों से शुरू करके पीछे की ओर काम करते हुए देखना सबसे आसान है। प्रत्येक पुनरावृत्ति की प्रारंभ में, दो इनपुट फ़ाइलें और एक आउटपुट फ़ाइल होगी। पुनरावृत्ति के अंत में, एक इनपुट फ़ाइल पूरी तरह से समाप्त हो जाएगी और अगले पुनरावृत्ति के लिए आउटपुट फ़ाइल बन जाएगी। वर्तमान आउटपुट फ़ाइल अगले पुनरावृत्ति के लिए एक इनपुट फ़ाइल बन जाएगी। शेष फ़ाइलें (3 फ़ाइल केस में केवल एक) केवल आंशिक रूप से उपभोग की गई हैं और उनके शेष रन अगले पुनरावृत्ति के लिए इनपुट होंगे।
 फ़ाइल 1 अभी-अभी खाली हुई और नई आउटपुट फ़ाइल बन गई। प्रत्येक इनपुट टेप पर एक रन छोड़ा गया है, और उन रन को एक साथ मर्ज करने से सॉर्ट की गई फ़ाइल बन जाएगी।<syntaxhighlight>
@@ Line 54: / Line 54: @@
 सही 3 फ़ाइल केस को देखते हुए, मर्ज किए गए पीछे की ओर काम करने के लिए रनों की संख्या: 1, 1, 2, 3, 5, ... एक फाइबोनैचि अनुक्रम का पता चलता है। 3 से अधिक फ़ाइलों का क्रम थोड़ा अधिक जटिल है; 4 फ़ाइलों के लिए, अंतिम स्थिति से शुरू करके और पीछे की ओर काम करते हुए, रन गिनती पैटर्न {1,0,0,0}, {0,1,1,1}, {1,0,2,2}, {3 है ,2,0,4}, {7,6,4,0}, {0,13,11,7}, {13,0,24,20}, ...।
-सब कुछ बेहतर ढंग से काम करने के लिए, अंतिम मर्ज चरण में प्रत्येक इनपुट फ़ाइल पर बिल्कुल एक रन होना चाहिए। यदि किसी इनपुट फ़ाइल में एक से अधिक रन हैं, तो दूसरे चरण की आवश्यकता होगी। नतीजतन, पॉलीफ़ेज़ मर्ज सॉर्ट को प्रारंभिक आउटपुट फ़ाइलों में इनपुट डेटा के रन के प्रारंभिक वितरण के बारे में चतुर होने की आवश्यकता है। उदाहरण के लिए, 13 रन वाली एक इनपुट फ़ाइल फ़ाइल 1 में 5 रन और फ़ाइल 2 में 8 रन लिखेगी।
+सब कुछ बेहतर ढंग से काम करने के लिए, अंतिम मर्ज चरण में प्रत्येक इनपुट फ़ाइल पर बिल्कुल एक रन होना चाहिए। यदि किसी इनपुट फ़ाइल में एक से अधिक रन हैं, तो दूसरे चरण की आवश्यकता होगी। परिणामस्वरूप, पॉलीफ़ेज़ मर्ज सॉर्ट को प्रारंभिक आउटपुट फ़ाइलों में इनपुट डेटा के रन के प्रारंभिक वितरण के बारे में चतुर होने की आवश्यकता है। उदाहरण के लिए, 13 रन वाली एक इनपुट फ़ाइल फ़ाइल 1 में 5 रन और फ़ाइल 2 में 8 रन लिखेगी।
-व्यवहार में, इनपुट फ़ाइल में पूर्ण वितरण के लिए आवश्यक रनों की सटीक संख्या नहीं होगी। इससे निपटने का एक तरीका एक आदर्श रन वितरण का अनुकरण करने के लिए काल्पनिक "डमी रन" के साथ वास्तविक वितरण को पैडिंग करना है।<ref name=Knuth1973/> एक डमी रन एक ऐसे रन की तरह व्यवहार करता है जिसमें कोई रिकॉर्ड नहीं होता है। एक या अधिक डमी रन को एक या अधिक वास्तविक रन के साथ मर्ज करने से केवल वास्तविक रन ही मर्ज होते हैं, और बिना किसी वास्तविक रन के एक या अधिक डमी रन को मर्ज करने से एकल डमी रन बनता है। एक अन्य दृष्टिकोण मर्ज ऑपरेशन के दौरान आवश्यकतानुसार डमी रन का अनुकरण करना है।<ref>https://www.fq.math.ca/Scanned/8-1/lynch.pdf {{Bare URL PDF|date=March 2022}}</ref>
+व्यवहार में, इनपुट फ़ाइल में पूर्ण वितरण के लिए आवश्यक रनों की सटीक संख्या नहीं होगी। इससे निपटने का एक तरीका एक आदर्श रन वितरण का अनुकरण करने के लिए काल्पनिक "डमी रन" के साथ वास्तविक वितरण को पैडिंग करना है।<ref name=Knuth1973/> एक डमी रन एक ऐसे रन की तरह व्यवहार करता है जिसमें कोई रिकॉर्ड नहीं होता है। एक या अधिक डमी रन को एक या अधिक वास्तविक रन के साथ मर्ज करने से केवल वास्तविक रन ही मर्ज होते हैं, और बिना किसी वास्तविक रन के एक या अधिक डमी रन को मर्ज करने से एकल डमी रन बनता है। एक अन्य दृष्टिकोण मर्ज ऑपरेशन के समय आवश्यकतानुसार डमी रन का अनुकरण करना है।<ref>https://www.fq.math.ca/Scanned/8-1/lynch.pdf {{Bare URL PDF|date=March 2022}}</ref>
-"इष्टतम" वितरण एल्गोरिदम के लिए रनों की संख्या पहले से जानने की आवश्यकता होती है। अन्यथा, अधिक सामान्य मामले में जहां रनों की संख्या पहले से ज्ञात नहीं होती है, "इष्टतम के करीब" वितरण एल्गोरिदम का उपयोग किया जाता है। कुछ वितरण एल्गोरिदम में रन को पुनर्व्यवस्थित करना शामिल है।<ref>http://i.stanford.edu/pub/cstr/reports/cs/tr/76/543/CS-TR-76-543.pdf {{Bare URL PDF|date=March 2022}}</ref> यदि रनों की संख्या पहले से ज्ञात है, तो मर्ज चरणों को शुरू करने से पहले केवल आंशिक वितरण की आवश्यकता होती है। उदाहरण के लिए, 3 फ़ाइल केस पर विचार करें, जो फ़ाइल_1 में n रन से शुरू होता है।  ''F<sub>i</sub>'' = ''F<sub>i</sub>''<sub>−1</sub> + F<sub>''i''−2</sub> को iवें [[फाइबोनैचि संख्या]] के रूप में परिभाषित करें। यदि ''n'' = ''F<sub>i</sub>'', तो ''F<sub>i</sub>''<sub>−2</sub> रन को File_2 पर ले जाएं, ''F<sub>i</sub>''<sub>−1</sub> रन को File_1 पर शेष छोड़ दें, जो एक आदर्श रन वितरण है। यदि ''F<sub>i</sub>'' < ''n'' < ''F<sub>i</sub>''<sub>+1</sub>, तो ''n''−''F<sub>i</sub>'' को File_2 पर चलाएं और ''F<sub>i</sub>''<sub>+1</sub>−''n'' को File_3 पर चलाएं। पहला मर्ज पुनरावृत्ति फ़ाइल_1 और फ़ाइल_2 से  ''n''−''F<sub>i</sub>'' रन को मर्ज करता है, ''n''−''F<sub>i</sub>'' मर्ज किए गए रन को ''F<sub>i</sub>''<sub>+1</sub>−''n''  रन में जोड़ता है जो पहले से ही File_3 में ले जाया गया है। File_1 Fi-2 रन शेष के साथ समाप्त होता है, File_2 खाली हो जाता है, और File_3 Fi−1 रन के साथ समाप्त होता है, फिर से एक आदर्श रन वितरण। 4 या अधिक फ़ाइलों के लिए, गणित अधिक जटिल है, लेकिन अवधारणा समान है।
+"इष्टतम" वितरण एल्गोरिदम के लिए रनों की संख्या पहले से जानने की आवश्यकता होती है। अन्यथा, अधिक सामान्य मामले में जहां रनों की संख्या पहले से ज्ञात नहीं होती है, "इष्टतम के निकट" वितरण एल्गोरिदम का उपयोग किया जाता है। कुछ वितरण एल्गोरिदम में रन को पुनर्व्यवस्थित करना सम्मलित है।<ref>http://i.stanford.edu/pub/cstr/reports/cs/tr/76/543/CS-TR-76-543.pdf {{Bare URL PDF|date=March 2022}}</ref> यदि रनों की संख्या पहले से ज्ञात है, तो मर्ज चरणों को शुरू करने से पहले केवल आंशिक वितरण की आवश्यकता होती है। उदाहरण के लिए, 3 फ़ाइल केस पर विचार करें, जो फ़ाइल_1 में n रन से शुरू होता है।  ''F<sub>i</sub>'' = ''F<sub>i</sub>''<sub>−1</sub> + F<sub>''i''−2</sub> को iवें [[फाइबोनैचि संख्या]] के रूप में परिभाषित करें। यदि ''n'' = ''F<sub>i</sub>'', तो ''F<sub>i</sub>''<sub>−2</sub> रन को File_2 पर ले जाएं, ''F<sub>i</sub>''<sub>−1</sub> रन को File_1 पर शेष छोड़ दें, जो एक आदर्श रन वितरण है। यदि ''F<sub>i</sub>'' < ''n'' < ''F<sub>i</sub>''<sub>+1</sub>, तो ''n''−''F<sub>i</sub>'' को File_2 पर चलाएं और ''F<sub>i</sub>''<sub>+1</sub>−''n'' को File_3 पर चलाएं। पहला मर्ज पुनरावृत्ति फ़ाइल_1 और फ़ाइल_2 से  ''n''−''F<sub>i</sub>'' रन को मर्ज करता है, ''n''−''F<sub>i</sub>'' मर्ज किए गए रन को ''F<sub>i</sub>''<sub>+1</sub>−''n''  रन में जोड़ता है जो पहले से ही File_3 में ले जाया गया है। File_1 Fi-2 रन शेष के साथ समाप्त होता है, File_2 खाली हो जाता है, और File_3 Fi−1 रन के साथ समाप्त होता है, फिर से एक आदर्श रन वितरण। 4 या अधिक फ़ाइलों के लिए, गणित अधिक जटिल है, लेकिन अवधारणा समान है।
 ==तुलना बनाम साधारण मर्ज सॉर्ट==
-प्रारंभिक वितरण के बाद, 4 फ़ाइलों का उपयोग करके एक सामान्य मर्ज सॉर्ट पूरे डेटासेट के 4 पुनरावृत्तियों में 16 एकल रिकॉर्ड रन को सॉर्ट करेगा, प्रारंभिक वितरण के बाद डेटासेट को सॉर्ट करने के लिए कुल 64 रिकॉर्ड को स्थानांतरित करेगा। 4 फ़ाइलों का उपयोग करके एक पॉलीफ़ेज़ मर्ज सॉर्ट 4 पुनरावृत्तियों में 17 एकल रिकॉर्ड को सॉर्ट करेगा, लेकिन चूंकि प्रत्येक पुनरावृत्ति लेकिन अंतिम पुनरावृत्ति केवल डेटासेट के एक अंश को स्थानांतरित करती है, यह प्रारंभिक के बाद डेटासेट को सॉर्ट करने के लिए कुल 48 रिकॉर्ड को ही स्थानांतरित वितरण करती है। इस मामले में, सामान्य मर्ज सॉर्ट फ़ैक्टर 2.0 है, जबकि पॉलीफ़ेज़ समग्र फ़ैक्टर ≈2.73 है।
+प्रारंभिक वितरण के पश्चात, 4 फ़ाइलों का उपयोग करके एक सामान्य मर्ज सॉर्ट पूरे डेटासेट के 4 पुनरावृत्तियों में 16 एकल रिकॉर्ड रन को सॉर्ट करेगा, प्रारंभिक वितरण के पश्चात डेटासेट को सॉर्ट करने के लिए कुल 64 रिकॉर्ड को स्थानांतरित करेगा। 4 फ़ाइलों का उपयोग करके एक पॉलीफ़ेज़ मर्ज सॉर्ट 4 पुनरावृत्तियों में 17 एकल रिकॉर्ड को सॉर्ट करेगा, लेकिन चूंकि प्रत्येक पुनरावृत्ति लेकिन अंतिम पुनरावृत्ति केवल डेटासेट के एक अंश को स्थानांतरित करती है, यह प्रारंभिक के पश्चात डेटासेट को सॉर्ट करने के लिए कुल 48 रिकॉर्ड को ही स्थानांतरित वितरण करती है। इस मामले में, सामान्य मर्ज सॉर्ट फ़ैक्टर 2.0 है, जबकि पॉलीफ़ेज़ समग्र फ़ैक्टर ≈2.73 है।
 यह समझाने के लिए कि कमी कारक सॉर्ट प्रदर्शन से कैसे संबंधित है, कमी कारक समीकरण हैं:<syntaxhighlight>
@@ Line 88: / Line 88: @@
     .53   4.28  6.00
     .53   4.87 16.00
-</syntaxhighlight>सामान्य तौर पर, जब 8 से कम फ़ाइलें होती हैं तो पॉलीफ़ेज़ मर्ज सॉर्ट सामान्य मर्ज सॉर्ट से बेहतर होता है, जबकि सामान्य मर्ज सॉर्ट लगभग 8 या अधिक फ़ाइलों पर बेहतर होने लगता है।<ref>{{Cite web|url=http://bluehawk.monmouth.edu/rclayton/web-pages/s06-503/esort.html|title=Advanced Programming I Lecture Notes}}</ref><ref>http://www.mif.vu.lt/~algis/dsax/DsSort.pdf {{Bare URL PDF|date=March 2022}}</ref>
+</syntaxhighlight>सामान्यतः, जब 8 से कम फ़ाइलें होती हैं तो पॉलीफ़ेज़ मर्ज सॉर्ट सामान्य मर्ज सॉर्ट से बेहतर होता है, जबकि सामान्य मर्ज सॉर्ट प्राय 8 या अधिक फ़ाइलों पर बेहतर होने लगता है।<ref>{{Cite web|url=http://bluehawk.monmouth.edu/rclayton/web-pages/s06-503/esort.html|title=Advanced Programming I Lecture Notes}}</ref><ref>http://www.mif.vu.lt/~algis/dsax/DsSort.pdf {{Bare URL PDF|date=March 2022}}</ref>
 ==संदर्भ==

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

पॉलीफ़ेज़ मर्ज सॉर्ट: Difference between revisions

Namespaces

More

Page actions

Revision as of 18:13, 15 July 2023

Contents

साधारण मर्ज सॉर्ट

पॉलीफ़ेज़ मर्ज

परफेक्ट 3 फ़ाइल पॉलीफ़ेज़ मर्ज सॉर्ट

पॉलीफ़ेज़ मर्ज सॉर्ट के लिए वितरण

तुलना बनाम साधारण मर्ज सॉर्ट

संदर्भ

अग्रिम पठन

बाहरी संबंध

Navigation

Navigation

Wiki tools

Wiki tools

Anonymous

Search

पॉलीफ़ेज़ मर्ज सॉर्ट: Difference between revisions

Revision as of 18:13, 15 July 2023

साधारण मर्ज सॉर्ट

पॉलीफ़ेज़ मर्ज

परफेक्ट 3 फ़ाइल पॉलीफ़ेज़ मर्ज सॉर्ट

पॉलीफ़ेज़ मर्ज सॉर्ट के लिए वितरण

तुलना बनाम साधारण मर्ज सॉर्ट

संदर्भ

अग्रिम पठन

बाहरी संबंध

Navigation

Wiki tools

Page tools

Other projects

Categories