Не удается заставить алгоритм сортировки по основанию работать в С++

Еще одно обновление, преобразованное в шаблон для типа массива. Массив Tmp теперь передается как параметр. Этапы копирования были убраны, и добавлена ​​вспомогательная функция для возврата буфера, в который попадают отсортированные данные. Протестировано с 4 миллионами 64-битных целых чисел без знака, это работает, но медленно. Наименьшее время достигается при numberOfBits = 4. numberOfBits больше не нужно точно делить количество битов на элемент.

Чтобы объяснить, почему MSD first работает медленно, я воспользуюсь аналогией со сортировщиком карт. Представьте, что у вас есть 1000 карточек, каждая из которых содержит 3 цифры от 000 до 999 в случайном порядке. Обычно вы проходите через сортировщик с 3-й цифрой, заканчивая 100 картами в каждой из ячеек, ячейка 0 содержит карты с «0», ... ячейка 9 содержит карты с «9». Затем вы объединяете карты из ячейки 0 в корзину 9 и снова пропускаете их через сортировщик, используя 2-ю цифру и снова используя 1-ю цифру, в результате чего получается отсортированный набор карточек. Это 3 прогона по 1000 карт в каждом, так что всего через сортировщик прошло 3000 карт.

Теперь снова начните со случайно упорядоченных карт и отсортируйте по 1-й цифре. Вы не можете объединить наборы, потому что карты с более высокими 1-ми цифрами, но более низкими 2-ми цифрами оказываются не по порядку. Итак, теперь вам нужно сделать 10 прогонов по 100 карт в каждом. В результате получается 100 комплектов по 10 карточек в каждом, которые вы снова пропускаете через сортировщик, в результате чего получается 1000 комплектов по 1 карточке в каждом, и теперь карточки отсортированы. Таким образом, количество карт, прошедших через сортировщик, по-прежнему равно 3000, как и выше, но вам нужно было сделать 111 прогонов (1 с набором из 1000 карт, 10 с набором из 100 карт, 100 с набором из 10 карт).

template <typename T>
void RadixSortMSD(size_t start, size_t end, 
          size_t numberOfBits, size_t currentBit, T input[], T tmp[])
{
    if((end - start) < 1)
        return;

    // adjust numberOfBits if currentBit close to end element
    if((currentBit + numberOfBits) > (8*sizeof(T)))
        numberOfBits = (8*sizeof(T)) - currentBit;

    // set numberOfBuckets
    size_t numberOfBuckets = 1 << numberOfBits;
    size_t bitMask = numberOfBuckets - 1;
    size_t shift = (8*sizeof(T)) - currentBit - numberOfBits;

    // create bucket info
    size_t *buckets = new size_t[numberOfBuckets+1];
    for(size_t p = 0; p < numberOfBuckets+1; p++)
        buckets[p] = 0;
    for(size_t p = start; p < end; p++)
        buckets[(input[p] >> shift) & bitMask]++;
    size_t m = start;
    for(size_t p = 0; p < numberOfBuckets+1; p++){
        size_t n = buckets[p];
        buckets[p] = m;
        m += n;
    }

    //sort the input array input and store it in array tmp   
    for (size_t p = start; p < end; p++){ 
        tmp[buckets[(input[p] >> shift) & bitMask]++] = input[p];
    }

    // restore bucket info
    for(size_t p = numberOfBuckets; p > 0; p--)
        buckets[p] = buckets[p-1];
    buckets[0] = start;

    // advance current bit
    currentBit += numberOfBits;
    if(currentBit < (8*sizeof(T))){
        //recurse on all the groups that have been created
        for(size_t p=0; p < numberOfBuckets; p++){
            RadixSortMSD(buckets[p], buckets[p+1],
                numberOfBits, currentBit, tmp, input);
        }
    }

    //free buckets
    delete[] buckets;
    return;
}

template <typename T>
T * RadixSort(T *pData, T *pTmp, size_t n)
{
size_t numberOfBits = 4;
    RadixSortMSD(0, n, numberOfBits, 0, pData, pTmp);
    // return the pointer to the sorted data
    if((((8*sizeof(T))+numberOfBits-1)/numberOfBits)&1)
        return pTmp;
    else
        return pData;
}