The Fastest Sorting Algorithm?
by Stefan Nilsson


Figure 1: 

Data: 100101, 011001, 100111, 001100, 011111, 110111

High                        Low
------------------------    ------------------------
000:                        000:
001: 001100, 001000         001:
010:                        010:
011: 011001, 011111         011:
100: 100101, 100111         100:
101:                        101:
110: 110111                 110:
111:                        111:

Batch: 100, 011, 001, 110


Figure 2: 

High                        Low
------------------------    ------------------------

000:                        000:
001: 001000                 001:
010:                        010:
011: 011001                 011:
100: 100101                 100: 001100
101:                        101:
110: 110111                 110:
111:                        111: 100111, 011111

Batch: 100, 011, 001, 110, 111, 100



Figure 3: 

High                        Low
------------------------    ------------------------
000:                        000:
001: 001000, 001100         001:
010:                        010:
011: 011001, 011111         011:
100: 100101, 100111         100:
101:                        101:
110: 110111                 110:
111:                        111:

Batch:  001, 011, 100, 100, 110, 111


Figure 4: 

Memory                        Active
------------------------      ------
Address Contents Pointer

0       134431   X----------> 0
1       938434      --------> 4
2       432754      |  -----> 6
3       292343      |  |
4       874944   X---  |
5       002345         |
6       654243   X------
7       112903


Figure 5: 

If the sequence x(1), x(2), ..., x(2k) is bitonic,
the two sequences

  L = min(x(1), x(k+1)), min(x(2), x(k+2)), min(x(k), x(2k))

and
  R = max(x(1), x(k+1)), max(x(2), x(k+2)), max(x(k), x(2k))


are also bitonic. Furthermore, each element of L is smaller
than or equal to each element of R.



Figure 6: 

X = 0, 2, 3, 5
Y = 2, 3, 6, 7

// Form a bitonic sequence S by reversing X and appending Y:
S = 5, 3, 2, 0, 2, 3, 6, 7

// Compute the min and max sequnces L and R:
L = min(5, 2), min(3, 3), min(2, 6), min(0, 7) = 2, 3, 2, 0
R = max(5, 2), max(3, 3), max(2, 6), max(0, 7) = 5, 3, 6, 7


Figure 7: 

A = 0101 0011 0010 0000 0000 0000 0000 0000   // 5 3 2 0 0 0 0 0
B = 0010 0011 0110 0111 0000 0000 0000 0000   // 2 3 6 7 0 0 0 0

// Compute a bitmask N, showing which elements of A that are
// smaller than or equal to the corresponding elements of B.
// M is a precomputed constant.

M = 1000 1000 1000 1000 1000 1000 1000 1000   // 8 8 8 8 8 8 8 8
N = ((B OR M) - A) AND M                      // 0 8 8 8 8 8 8 8
N = N - (N>>3)                                // 0 7 7 7 7 7 7 7

// Compute the max and min sequence and concatenate them.

Z =    (B AND N)                              // 0 3 6 7 0 0 0 0
    OR (A - (A AND N))                        // 5 0 0 0 0 0 0 0
    OR ((A AND N)>>16)                        // 0 0 0 0 0 3 2 0
    OR ((B - (B AND N))>>16)                  // 0 0 0 0 2 0 0 0







3


