Batcher's Merge-Exchange Sort

Question

¿Alguien tiene una buena guía/explicación de Batcher's Merge-Exchange Sort?

Este no es el mismo algoritmo que el tipo bitónico de Batcher o el tipo de fusión impar de Batcher, aunque muchos artículos pretenden que sí lo es.

Answer 1

Donald Knuth, El arte de la programación de computadoras, algoritmo 5.2.2M (volumen III, página 111).

Ken Batcher (1968), "Sorting networks and their application", Proc. AFIPS Spring Joint Computer Conference 32: 307-314.

Answer 2

De http://www.eli.sdsu.edu/courses/spring96/cs662/notes/batcher/batcher.html

Input: N and array A[1:N] of items to sort 

set T = Ceiling(lg(N)) 

for P = 2T-1, 2T-2, 2T-3, ..., 1 do 
R = 0, D = P 
for Q = 2T-1, 2T-2, 2T-3, ..., P do 
for (K = 1 to N - D) and ((K-1) P) = R do in parallel 
if A[K] > A[K + D] then 
swap(A[K], A[K + D ]) 
end if 
end for 
D = Q - P 
R = P 
end for 
end for 


(K + 1) P means logical and of K and P 

If number of processors is less than N than the swap becomes a merge 

This site tiene una visualización de este algoritmo

Answer 3

aplicación simple :)

int FloorLog2(int value) 
{ 
    int result = -1; 
    for (int i = 1; i < value; i <<= 1, ++result); 
    return result; 
} 

void BatcherSort(int* array, int length) 
{ 
    int t = FloorLog2(length); 
    int p0 = (1 << t); 
    int p = p0; 

    do 
    { 
     int q = p0; 
     int r = 0; 
     int d = p; 

     while (r == 0 || q != p) 
     { 
      if (r != 0) 
      { 
       d = q - p; 
       q >>= 1; 
      } 

      for (int i = 0; i < length - d; ++i) 
      { 
       if (((i & p) == r) && array[i] > array[i + d]) 
       { 
        int swap = array[i]; 
        array[i] = array[i + d]; 
        array[i + d] = swap; 
       } 
      } 

      r = p; 
     } 

     p >>= 1; 
    } 
    while (p > 0); 
}