बैचर विषम-सम मर्जसॉर्ट

बैचर विषम-सम मर्जसॉर्ट

Visualization of the odd–even mergesort network with eight inputs
Class	Sorting algorithm
Data structure	Array
Worst-case performance	$O(\log ^{2}(n))$ parallel time
Best-case performance	$O(\log ^{2}(n))$ parallel time
Average performance	$O(\log ^{2}(n))$ parallel time
Worst-case space complexity	$O(n\log ^{2}(n))$ non-parallel time

बैचर का सम-विषम मर्ज सॉर्ट आकार O(n (लॉग एन) के नेटवर्क को सॉर्ट करने के लिए क्यों बैच द्वारा तैयार किया गया एक सामान्य निर्माण है²) और गहराई O((लॉग एन)²), जहां n क्रमबद्ध किए जाने वाले आइटमों की संख्या है। यद्यपि यह स्पर्शोन्मुख रूप से इष्टतम नहीं है, डोनाल्ड नुथ ने 1998 में सॉर्टिंग नेटवर्क#ऑप्टिमल सॉर्टिंग नेटवर्क के संबंध में निष्कर्ष निकाला कि बैचर की विधि बहुत बेहतर है, जब तक कि एन पृथ्वी पर सभी कंप्यूटरों की कुल मेमोरी क्षमता से अधिक न हो जाए! इसे दूसरी जीपीयू रत्न बुक द्वारा लोकप्रिय बनाया गया है, ग्राफ़िक्स-प्रोसेसिंग हार्डवेयर पर यथोचित कुशल सॉर्टिंग करने का एक आसान तरीका।

स्यूडोकोड

तुलना और क्रमबद्ध किए जाने वाले तत्वों के सूचकांकों की गणना करने के लिए विभिन्न पुनरावर्ती और पुनरावृत्तीय योजनाएं संभव हैं। यह n तत्वों को क्रमबद्ध करने के लिए सूचकांक उत्पन्न करने की एक पुनरावृत्तीय तकनीक है:

# note: the input sequence is indexed from 0 to (n-1)
for p = 1, 2, 4, 8, ... # as long as p < n
  for k = p, p/2, p/4, p/8, ... # as long as k >= 1
    for j = mod(k,p) to (n-1-k) with a step size of 2k
      for i = 0 to min(k-1, n-j-k-1) with a step size of 1
        if floor((i+j) / (p*2)) == floor((i+j+k) / (p*2))
          compare and sort elements (i+j) and (i+j+k)

पार्टनर नोड इंडेक्स की गैर-पुनरावर्ती गणना भी संभव है।

यह भी देखें

• बिटोनिक सॉर्टर
• जोड़ीवार छँटाई नेटवर्क

बाहरी संबंध

• Odd–even mergesort at hs-flensburg.de
• Odd-even mergesort network generator Interactive Batcher's Odd-Even merge-based sorting network generator.