सैंपलसॉर्ट

सैंपलसॉर्ट, डिवाइड एंड कंकर एल्गोरिथ्म पर आधारित एक सॉर्टिंग एल्गोरिथ्म है, जिसका उपयोग प्रायः पैरलेल प्रोसेसिंग सिस्टम में किया जाता है। पारंपरिक डिवाइड एंड कंकर एल्गोरिथ्म, ऐरे को सब-इंटरवल या बकेट में विभाजित करता है। फिर इस बकेट को अलग-अलग क्रमबद्ध किया जाता है और एक साथ जोड़ दिया जाता है। यद्यपि, यदि ये ऐरे गैर-समान रूप से वितरित किए गए है, तो इन सॉर्टिंग एल्गोरिदम का प्रदर्शन अत्यधिक सीमा तक कम हो सकता है। सैंपलसॉर्ट इस समस्या का समाधान करने में सक्षम है जिसमें n-एलिमेंट सीक्वन्स के लिए एक s आकार का सैम्पल चुनकर तथा उस सैंपल को सॉर्ट करने के उपरांत p-1 < s एलेमेन्ट को परिणाम से चुनकर बकेट की रेंज निर्धारित की जाती है। ये एलमेंट (जिन्हें स्प्लिटर्स कहा जाता है) फिर ऐरे को लगभग p समान बकेट में विभाजित करते हैं। सैंपलसॉर्ट का वर्णन 1970 के लेख, सैंपलसॉर्ट: ए सैंपलिंग अप्रोच टू मिनिमल स्टोरेज ट्री सॉर्टिंग में डब्ल्यू. डी. फ्रेज़र और ए. सी. मैककेलर द्वारा किया गया है।

एल्गोरिथम

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

सैंपलसॉर्ट कार्यान्वयन तैयार करने के लिए, हमें p बकेट की संख्या तय करने की आवश्यकता होती है। जब यह किया जाता है, तो वास्तविक एल्गोरिदम तीन चरणों में संचालित होता है:

1. सैम्पल p−1 इनपुट से तत्व (स्प्लिटर्स)। सॉर्ट करें; आसन्न स्प्लिटर्स का प्रत्येक युग्म फिर एक बकेट को परिभाषित करता है।
2. डेटा लूप करें, प्रत्येक तत्व को उपयुक्त बकेट में रखें। (इसका तात्पर्य यह हो सकता है: इसे मल्टीप्रोसेसर सिस्टम में एक प्रोसेसर को भेजें।)
3. प्रत्येक बकेट को क्रमबद्ध करें.

पूर्ण क्रमबद्ध आउटपुट बकेट का संयोजन है।

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

स्यूडोकोड

निम्नलिखित सूची उपर्युक्त तीन चरण वाले एल्गोरिदम को स्यूडोकोड के रूप में प्रदर्शित करती है और दिखाती है कि एल्गोरिदम सिद्धांत रूप में कैसे कार्य करता है। निम्नांकित में, A अवर्गीकृत डेटा है, k ओवरसैंपलिंग कारक है, जिस पर बाद में चर्चा की गई है, और p स्प्लिटर्स की संख्या है.

function sampleSort(A[1..n], k, p)
    // if average bucket size is below a threshold switch to e.g. quicksort
    if n / k < threshold then smallSort(A) 
    /* Step 1 */
    select S = [S1, ..., S(p−1)k] randomly from // select samples
    sort S // sort sample
    [s0, s1, ..., sp−1, sp] <- [-∞, Sk, S2k, ..., S(p−1)k, ∞] // select splitters
    /* Step 2 */
    for each a in A
        find j such that sj−1 < a <= sj
        place a in bucket bj
    /* Step 3 and concatenation */
    return concatenate(sampleSort(b1), ..., sampleSort(bk))

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

कम्प्लेक्सिटी

$p$ प्रोसेसर समानांतर कार्यान्वयन के लिए बिग ओ अंकन में दी गई कम्प्लेक्सिटी:

स्प्लिटर्स खोजें.

$O\left({\frac {n}{p}}+\log(p)\right)$

बकेट को भेजें.

$O(p)$ सभी नोड्स को रीड करने के लिए

$O(\log(p))$ ब्रॉड्कैस्टिंग के लिए

$O\left({\frac {n}{p}}\log(p)\right)$ सभी कीज के लिए बाइनरी सर्च हेतु

$O\left({\frac {n}{p}}\right)$ बकेट में 'की' भेजने के लिए

बकेट को क्रमबद्ध करें.

$O\left(c\left({\frac {n}{p}}\right)\right)$ जहाँ $c(n)$ अंतर्निहित अनुक्रमिक सॉर्टिंग पद्धति की कम्प्लेक्सिटी है। प्रायः $c(n)=n\log(n)$.

इस एल्गोरिथम द्वारा की गई तुलनाओं की संख्या, सूचना सैद्धांतिक इष्टतम $\log _{2}(n!)$ के निकट पहुंचती है बड़े इनपुट अनुक्रमों के लिए. फ़्रेज़र और मैककेलर द्वारा किए गए प्रयोगों में, एल्गोरिदम को क्विकसॉर्ट की तुलना में 15% कम तुलना की आवश्यकता थी।

डेटा सैंपलिंग

डेटा का सैम्पल विभिन्न विधियों से लिया जा सकता है। कुछ विधियों में सम्मिलित हैं:

1. समान दूरी वाले सैम्पल चुनें.
2. यादृच्छिक विधि से चयनित सैम्पल चुनें.

ओवरसैंपलिंग

ओवरसैंपलिंग अनुपात यह निर्धारित करता है कि स्प्लिटर्स को निर्धारित करने से पहले सैम्पल के रूप में कितनी बार अधिक डेटा एलमेंट को प्राप्त करना है। इसका लक्ष्य डेटा के वितरण का अच्छा प्रतिनिधित्व प्राप्त करना है। यदि डेटा मान व्यापक रूप से वितरित हैं, जिसमें कई डुप्लिकेट मान नहीं हैं, तो एक छोटा सैम्पल अनुपात पर्याप्त है। अन्य परिस्थितियों में जहां वितरण में कई डुप्लिकेट हैं, एक बड़ा ओवरसैंपलिंग अनुपात आवश्यक होगा। आदर्श स्थिति में, चरण 2 के उपरांत, प्रत्येक बकेट में $n/p$ एलेमेन्ट सम्मिलित होता है। इस परिप्रेक्ष्य में, किसी भी बकेट को सॉर्ट करने में अन्य की तुलना में अधिक समय नहीं लगता है, क्योंकि सभी बकेट समान आकार के होतें हैं।

आवश्यकता से $k$ बार अधिक सैंपल निकालने के उपरांत, सैंपल सॉर्ट किया जाता है। इसके उपरांत, बकेट सीमाओं के रूप में उपयोग किए जाने वाले स्प्लिटर्स स्थिति में $k,2k,3k,\dots ,(p-1)k$ सैम्पल हैं। यह केवल चयन करने की तुलना में अच्छे स्प्लिटर्स के लिए उपयुक्त अनुमान प्रदान करता है तथा $p$ यादृच्छिक विधि से विभाजित हो जाता है।

बकेट आकार अनुमान

परिणामी सैम्पल आकार के साथ, अपेक्षित बकेट आकार और विशेष रूप से एक निश्चित आकार से अधिक बकेट की संभावना का अनुमान लगाया जा सकता है। निम्नलिखित यह दिखाएगा कि ओवरसैंपलिंग कारक के लिए $S\in \Theta \left({\dfrac {\log n}{\epsilon ^{2}}}\right)$ किसी भी बकेट में इससे अधिक न होने की प्रायिकता $(1+\epsilon )\cdot {\dfrac {n}{p}}$ $1-{\dfrac {1}{n}}$ एलमेंट से ज्यादा है।

यह सिद्ध करने के लिए हम सॉर्टिड सीक्वन्स $\langle e_{1},\dots ,e_{n}\rangle$ के रूप में इनपुट लेते हैं। प्रोसेसर को $(1+\epsilon )\cdot n/p$ से अधिक एलमेंट प्राप्त करने के लिए, $(1+\epsilon )\cdot n/p$ लंबाई का एक ऐसा उपसूत्र होना आवश्यक है, जिसमें से अधिकतम S सैंपल्स चुने जाते हैं। ये तथ्य $P_{\text{fail}}$ संभाव्यता का गठन करते हैं। इसे यादृच्छिक चर के रूप में निम्नलिखित रूप से दर्शाया जा सकता है:

$$X_{i}:={\begin{cases}1,&{\text{if }}s_{i}\in \left\langle e_{j},\dots ,e_{j}+(1+\epsilon )\cdot {\dfrac {n}{p}}\right\rangle \\0,&{\text{otherwise}}\end{cases}},X:=\sum _{i=0}^{S\cdot p-1}X_{i}$$

के अपेक्षित मूल्य के लिए $X_{i}$ धारण करता है:

$$E(X_{i})=P(X_{i}=1)={\dfrac {1+\epsilon }{p}}$$

इसका उपयोग अनुमान लगाने के लिए किया जाएगा $P_{\text{fail}}$:

$$P(X<S)\approx P(X<(1-\epsilon ^{2})S)=P(X<(1-\epsilon )E(X))$$

अब चेर्नॉफ़ बाध्य का उपयोग करके, इसे दिखाया जा सकता है:

$$P_{\text{fail}}=n\cdot P(X<S)\leq n\cdot \exp \left({\dfrac {-\epsilon ^{2}\cdot S}{2}}\right)\leq n\cdot {\dfrac {1}{n^{2}}}{\text{ for }}S\geq {\dfrac {4}{\epsilon ^{2}}}\ln n$$

कई इडेंटिकल 'की'(key)

कई इडेंटिकल 'की' के परिप्रेक्ष्य में, एल्गोरिदम कई पुनरावर्तन स्तरों से गुजरता है जहां अनुक्रमों को क्रमबद्ध किया जाता है, क्योंकि पूरे अनुक्रम में समान कुंजियाँ होती हैं। समानता बकेट प्रारंभ करके इसका प्रतिकार किया जा सकता है। पोल के बराबर एलमेंट को उनके संबंधित समानता बकेट में क्रमबद्ध किया जाता है, जिसे केवल एक अतिरिक्त सशर्त शाखा के साथ कार्यान्वित किया जा सकता है। समानता के बकेट आगे क्रमबद्ध नहीं हैं। यह काम करता है, क्योंकि कुंजियाँ अधिक से अधिक $n/k$ घटित होती हैं। इसमे समय के निर्णायक बनने की संभावना है।

पैरलेल सिस्टम में उपयोग

समानांतर सैम्पल सॉर्ट का उदाहरण $p=3$ प्रोसेसर और एक ओवरसैंपलिंग कारक $k=3$.

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

पैरललीकरण को प्रत्येक प्रोसेसर या नोड के लिए विभाजित करके अंगीकृत किया जाता है, जहां बकेटों की संख्या प्रोसेसरों की संख्या $p$ के बराबर होती है। सैंपलसॉर्ट पैरलल सिस्टम में प्रभावी होता है क्योंकि प्रत्येक प्रोसेसर को लगभग समान बकेट का आकार $n/p$ प्राप्त होता है। बकेट समानांतर सॉर्ट किए जाते हैं, इसलिए प्रोसेसर लगभग समान समय में सॉर्टिंग पूरा कर जाते हैं, इससे किसी प्रोसेसर को दूसरों के लिए रुकने की आवश्यकता नहीं होती है।

वितरित सिस्टम पर, स्प्लिटर्स का चयन $k$ एलमेंट को प्रत्येक प्रोसेसर पर लेकर किया जाता है, परिणामस्वरूप बने $kp$ एलमेंट को वितरित सॉर्टिंग एल्गोरिदम के साथ सॉर्ट किया जाता है, हर $k$-वां तत्व चुना जाता है और परिणाम को सभी प्रोसेसरों को ब्रॉडकास्ट किया जाता है। यह $p$ प्रोसेसरों पर $kp$ एलमेंट को सॉर्ट करने के लिए $T_{\text{sort}}(kp,p)$ का खर्च होता है, साथ ही $p$ चुने गए स्प्लिटर्स को $p$ प्रोसेसरों को वितरित करने के लिए $T_{\text{allgather}}(p,p)$ का भी कॉस्ट होता है।

परिणामकारी स्प्लिटर्स के साथ, प्रत्येक प्रोसेसर अपने इनपुट डेटा को स्थानीय बकेट में रखता है। इसके लिए बाइनरी सर्च के साथ ${\mathcal {O}}(n/p\log p)$ का समय लगता है। इसके बाद, स्थानीय बकेट्स प्रोसेसरों को पुनः वितरित किए जाते हैं। प्रोसेसर $i$ सभी अन्य प्रोसेसरों के स्थानीय बकेट्स $b_{i}$ को प्राप्त करता है और इन्हें स्थानीय रूप से सॉर्ट करता है। वितरण $T_{\text{all-to-all}}(N,p)$ समय लेता है, जहां $N$ सबसे बड़े बकेट का आकार है। स्थानीय सॉर्ट $T_{\text{localsort}}(N)$ का समय लेता है।

1990 के दशक में कनेक्शन मशीन सुपरकंप्यूटर पर किए गए प्रयोग ने दिखाया कि सैंपलसॉर्ट बड़े डेटासेट को सॉर्ट करने में विशेष रूप से अच्छा है, क्योंकि इसका इंटरप्रोसेसर संचार ओवरहेड कम होता है। हाल के GPUs पर, इस एल्गोरिदम का प्रयोग उसके विकल्पों की तुलना में कम प्रभावी हो सकता है।

सैम्पल सॉर्ट का एफीसिएंट कार्यान्वयन

सुपर स्केलर सैंपलसॉर्ट का एनिमेटेड उदाहरण। प्रत्येक चरण में, जिन संख्याओं की तुलना की जाती है उन्हें नीले रंग से चिह्नित किया जाता है और जो संख्याएं अन्यथा पढ़ी या लिखी जाती हैं उन्हें लाल रंग से चिह्नित किया जाता है।

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

प्रत्येक रिकर्सन चरण में, डेटा को डिवाइड विधि से अन्य ऐरे में कॉपी किया जाता है। यदि डेटा अंतिम रिकर्सन चरण में अस्थायी ऐरे में है, तो डेटा को मूल ऐरे में वापस कॉपी किया जाता है।

बकेट का निर्धारण

किसी तुलना-आधारित सॉर्टिंग एल्गोरिदम में तुलना की संचार ऑपरेशन सबसे प्रदर्शन-मुख्य भाग होती है। सैंपलसॉर्ट में यह तत्व के लिए बकेट निर्धारित करने के लिए होती है। इसमें प्रत्येक तत्व के लिए $\log k$ समय लगता है।

सुपर स्केलर सैंपल सॉर्ट एक बैलन्स सर्च ट्री का उपयोग करता है जो स्वतः में एक एरे t में रखा गया होता है। रूट ट्री 0 पर रखा जाता है, $t_{i}$ का बाईं उत्तरधारी $t_{2i}$ पर रखा जाता है और दाईं उत्तरधारी $t_{2i+1}$ पर रखा जाता है। ट्री t को दिया गया है, एल्गोरिदम एलमेंट $a_{i}$ का बकेट नंबर j निम्नलिखित विधि से निर्धारित करता है (यहां स्वीकृति है कि $a_{i}>t_{j}$ का मूल्य 1 होगा यदि यह सत्य है और 0 होगा यदि यह सत्य नहीं है):

j := 1
repeat log2(p) times
    j := 2j + (a > tj)
j := j − p + 1

बकेटों की संख्या k कंपाइल समय पर ज्ञात होती है, इसलिए कंपाइलर इस लूप को अनरोल कर सकता है। तुलना ऑपरेशन को प्रेडिकेटेड इंस्ट्रक्शन्स के साथ लागू किया जाता है। इससे ब्रांच मिसप्रिडिक्शन नहीं होती है, जो तुलना ऑपरेशन को काफी धीमा बना सकता है।

विभाजन

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

इस दोहराने वाले तुलना को टालने के लिए, सुपर स्केलर सैंपल सॉर्ट एक अतिरिक्त एरे $o$ (जिसे ऑरेकल कहा जाता है) का उपयोग करता है जो प्रत्येक तत्व के एक बकेट से सम्बंधित होता है। पहले, एल्गोरिदम $o$ के संदर्भ को निर्धारित करके यह निर्धारित करता है, फिर बकेट का आकार निर्धारित करके तत्वों को $o$ द्वारा निर्धारित बकेट में रखता है। एरे $o$ भी संग्रह स्थान में खर्च करता है, लेकिन क्योंकि इसमें केवल $n\cdot \log k$ बिट संभावित होते हैं, इन खर्चों को इनपुट एरे के अनुपात में छोटा माना जा सकता है।

इन-प्लेस सैंपलसॉर्ट

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

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

इस एल्गोरिदम का एक स्पष्ट नुकसान यह है कि यह प्रत्येक तत्व को दो बार पढ़ता और लिखता है, एक बार वर्गीकरण चरण में और एक बार ब्लॉक क्रमपरिवर्तन चरण में। यद्यपि, एल्गोरिथ्म अन्य अत्याधुनिक इन-प्लेस प्रतिस्पर्धियों की तुलना में तीन गुना तेज और अन्य अत्याधुनिक अनुक्रमिक प्रतिस्पर्धियों की तुलना में 1.5 गुना तेज प्रदर्शन करता है। जैसा कि सैम्पल के बारे में पहले ही ऊपर चर्चा की जा चुकी है, बाद के तीन चरणों के बारे में आगे विस्तार से बताया जाएगा।

स्थानीय वर्गीकरण

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

ब्लॉक क्रमपरिवर्तन

सबसे पहले, एक उपसर्ग योग ऑपरेशन किया जाता है जो बकेट की सीमाओं की गणना करता है। यद्यपि, चूंकि इस चरण में केवल पूर्ण ब्लॉकों को स्थानांतरित किया जाता है, सीमाओं को ब्लॉक आकार के गुणक तक गोल किया जाता है और एक एकल अतिप्रवाह बफर आवंटित किया जाता है। ब्लॉक क्रमपरिवर्तन शुरू करने से पहले, कुछ खाली ब्लॉकों को इसकी बकेट के अंत में ले जाना पड़ सकता है। इसके बाद, एक सूचक लिखें $w_{i}$ बकेट की शुरुआत पर सेट है $b_{i}$ प्रत्येक बकेट के लिए उपऐरे और एक पठन सूचक $r_{i}$ बकेट में अंतिम गैर-खाली ब्लॉक पर सेट किया गया है $b_{i}$ प्रत्येक बकेट के लिए उपऐरे.

कार्य विवाद को सीमित करने के लिए, प्रत्येक प्रोसेसर को एक अलग प्राथमिक बकेट सौंपा गया है $b_{prim}$ और दो स्वैप बफ़र्स जो प्रत्येक ब्लॉक को पकड़ सकते हैं। प्रत्येक चरण में, यदि दोनों स्वैप बफ़र खाली हैं, तो प्रोसेसर रीड पॉइंटर को कम कर देता है $r_{prim}$ इसके प्राथमिक बकेट का और ब्लॉक को पढ़ता है $r_{prim-1}$ और इसे अपने स्वैप बफ़र्स में से एक में रखता है। गंतव्य बकेट निर्धारित करने के बाद $b_{dest}$ ब्लॉक के पहले तत्व को वर्गीकृत करके, यह राइट पॉइंटर को बढ़ाता है $w_{dest}$, पर ब्लॉक पढ़ता है $w_{dest-1}$ दूसरे स्वैप बफ़र में और ब्लॉक को उसके गंतव्य बकेट में लिखता है। अगर $w_{dest}>r_{dest}$, स्वैप बफ़र्स फिर से खाली हैं। अन्यथा स्वैप बफ़र्स में बचे ब्लॉक को उसके गंतव्य बकेट में डालना होगा।

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

सफ़ाई

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

यह भी देखें

• फ्लैशसॉर्ट
• जल्दी से सुलझाएं

बाहरी संबंध

Frazer and McKellar's samplesort and derivatives:

• Frazer and McKellar's original paper
• DOI.org
• DOI.org

Adapted for use on parallel computers:

• http://citeseer.ist.psu.edu/91922.html
• http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.49.214