Php binary radix sort implementation

Question

I'm trying to implement a radix sort in binary, because i want to check if the speed of bit shifting operations counterbalance the number of steps required. My counting sort seems to work, but as soon as i have several passes for the radix sort, the result break. Any help greatly appreciated.

/*
* bits is to store the value of the current digit for each number in the input array
*/
function countSort(&$arr, $digit) {
    $bits = $output = array_fill(0, NB_ELEMS, 0);
    $count = [0,0];
  
    // Store count of occurrences in count[]  
    for ($i = 0; $i < NB_ELEMS; $i++) {
        $nb = $arr[$i];
        $bit = ($nb >> $digit) & 1;
        $bits[$i] = $bit;
        $count[$bit]++;
    }
    // Cumulative count
    $count[1] = NB_ELEMS;

    // Rearranging
    for ($i = 0; $i < NB_ELEMS; $i++) {
        $nb = $arr[$i];
        $bit = $bits[$i];
        $output[$count[$bit] - 1] = $nb;
        $count[$bit]--;
    }

    // Switch arrays
    $arr = $output;
}

function radixSort(&$arr, $nb_digits) {      
    // Do counting sort for every binary digit
    for($digit = 0; $digit < $nb_digits; $digit++) {
        countSort($arr, $digit);
    }
}

$tab = [4,3,12,8,7];
$max_value = max($tab);
$nb_digits = floor(log($max_value, 2)) + 1;
radixSort($tab, $nb_digits);

Answer 1

Ok, thanks to a friend, i found my problem : the counting sort implementation which i use stacks the same digit numbers using the counter as top index, and then decrementing it. And that's ok for counting sort (so one iteration), but it scrambles everything when you use it in radix sort (multiple counting sort iterations).

So i used instead a method in which you shift your counters one time right, which gives you for the n+1 digit your starting point, and then increment it.

And boom you're good to go.

function countSort2(&$arr, $digit) {
    $bits = $output = array_fill(0, NB_ELEMS, 0); // output array  
    $count = [0,0];
  
    // Store count of occurrences in count[]  
    for ($i = 0; $i < NB_ELEMS; $i++) {
        $nb = $arr[$i];
        $bit = ($nb >> $digit) & 1;
        $bits[$i] = $bit;
        $count[$bit]++;
    }
    // Cumulative count shifted
    $count[1] = $count[0];
    $count[0] = 0;

    // Rearranging
    for ($i = 0; $i < NB_ELEMS; $i++) {
        $nb = $arr[$i];
        $bit = $bits[$i];
        $output[$count[$bit]] = $nb;
        $count[$bit]++;
    }

    // Switch arrays
    $arr = $output;
}  

I also made some tests (1M items, max value 1M, 100 iterations), and a method storing values instead of counting them, and merging thereafter seems twice as fast (function just after that). Anyway, both methods are far under native sort performance. Any comment appreciated

function byDigitSortArrayMerge(&$arr, $digit) {
    $output = array_fill(0, NB_ELEMS - 1, 0); // output array  
    $bits = array_fill(0, NB_ELEMS - 1, 0); // output array
    $by_bit = [[], []];
  
    // Store count of occurrences in count[]  
    for ($i = 0; $i < NB_ELEMS; $i++) {
        $nb = $arr[$i];
        $bit = ($nb >> $digit) & 1;
        $by_bit[$bit][] = $nb;
    }
    $arr = array_merge($by_bit[0], $by_bit[1]);
}