PHP usort переупорядочивает массив, значение сортировки одинаково для всех

Ага, дело в преобразовании Шварца.

В основном он состоит из трех шагов:

1. украшать; вы превращаете каждое значение в массив со значением в качестве первого элемента и ключом/индексом в качестве второго
2. сортировать (как обычно)
3. неукрашенный; вы отменяете шаг 1

Вот он (я настроил его для вашего конкретного варианта использования):

function decorate(&$v, $k)
{
    $v['authn_weight'] = array($v['authn_weight'], $k);
}

function undecorate(&$v, $k)
{
    $v['authn_weight'] = $v['authn_weight'][0];
}

array_walk($a, 'decorate');
usort($a, 'weightSortImplementation');
array_walk($a, 'undecorate');

Хитрость заключается в следующем утверждении:

array($x, 0) < array($x, 1)

Это то, что поддерживает правильный порядок вашего массива. И рекурсия не требуется :)

Из документации:

Если два элемента сравниваются как равные, их относительный порядок в отсортированном массиве не определен.

Вы можете использовать эту функцию [source], которая сохраняет порядок в случае равенства двух элементов:

function mergesort(&$array, $cmp_function = 'strcmp') {
    // Arrays of size < 2 require no action.
    if (count($array) < 2) return;
    // Split the array in half
    $halfway = count($array) / 2;
    $array1 = array_slice($array, 0, $halfway);
    $array2 = array_slice($array, $halfway);
    // Recurse to sort the two halves
    mergesort($array1, $cmp_function);
    mergesort($array2, $cmp_function);
    // If all of $array1 is <= all of $array2, just append them.
    if (call_user_func($cmp_function, end($array1), $array2[0]) < 1) {
        $array = array_merge($array1, $array2);
        return;
    }
    // Merge the two sorted arrays into a single sorted array
    $array = array();
    $ptr1 = $ptr2 = 0;
    while ($ptr1 < count($array1) && $ptr2 < count($array2)) {
        if (call_user_func($cmp_function, $array1[$ptr1], $array2[$ptr2]) < 1) {
            $array[] = $array1[$ptr1++];
        }
        else {
            $array[] = $array2[$ptr2++];
        }
    }
    // Merge the remainder
    while ($ptr1 < count($array1)) $array[] = $array1[$ptr1++];
    while ($ptr2 < count($array2)) $array[] = $array2[$ptr2++];
    return;
}