The Fastest Sorting Algorithm?
By Stefan Nilsson, April 01, 2000
Which sorting algorithm is the fastest? Stefan presents his answer to this age-old question.
Apr00: The Fastest Sorting Algorithm?
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
Figure 7: Implementing the computation of Figure 6 in parallel with standard operations only.
