[ACCEPTED]-Radix Sort implemented in C++-radix-sort

I think you're severely overcomplicating 11 your solution. You can implement radix using 10 the single array received in the input, with 9 the buckets in each step represented by 8 an array of indices that mark the starting 7 index of each bucket in the input array.

In 6 fact, you could even do it recursively:

// Sort 'size' number of integers starting at 'input' according to the 'digit'th digit
// For the parameter 'digit', 0 denotes the least significant digit and increases as significance does
void radixSort(int* input, int size, int digit)
{
    if (size == 0)
        return;

    int[10] buckets;    // assuming decimal numbers

    // Sort the array in place while keeping track of bucket starting indices.
    // If bucket[i] is meant to be empty (no numbers with i at the specified digit),
    // then let bucket[i+1] = bucket[i]

    for (int i = 0; i < 10; ++i)
    {
        radixSort(input + buckets[i], buckets[i+1] - buckets[i], digit+1);
    }
}

Of 5 course buckets[i+1] - buckets[i] will cause a buffer overflow when 4 i is 9, but I omitted the extra check or 3 readability's sake; I trust you know how 2 to handle that.

With that, you just have 1 to call radixSort(testcases, sizeof(testcases) / sizeof(testcases[0]), 0) and your array should be sorted.

To speed up the process with better memory 14 management, create a matrix for the counts 13 that get converted into indices by making 12 a single pass over the array. Allocate a 11 second temp array the same size as the original 10 array, and radix sort between the two arrays 9 until the array is sorted. If an odd number 8 of radix sort passes is performed, then 7 the temp array will need to be copied back 6 to the original array at the end.

To further 5 speed up the process, use base 256 instead 4 of base 10 for the radix sort. This only 3 takes 1 scan pass to create the matrix and 2 4 radix sort passes to do the sort. Example 1 code:

typedef unsigned int uint32_t;

uint32_t * RadixSort(uint32_t * a, size_t count)
{
size_t mIndex[4][256] = {0};            // count / index matrix
uint32_t * b = new uint32_t [COUNT];    // allocate temp array
size_t i,j,m,n;
uint32_t u;
    for(i = 0; i < count; i++){         // generate histograms
        u = a[i];
        for(j = 0; j < 4; j++){
            mIndex[j][(size_t)(u & 0xff)]++;
            u >>= 8;
        }       
    }
    for(j = 0; j < 4; j++){             // convert to indices
        m = 0;
        for(i = 0; i < 256; i++){
            n = mIndex[j][i];
            mIndex[j][i] = m;
            m += n;
        }       
    }
    for(j = 0; j < 4; j++){             // radix sort
        for(i = 0; i < count; i++){     //  sort by current lsb
            u = a[i];
            m = (size_t)(u>>(j<<3))&0xff;
            b[mIndex[j][m]++] = u;
        }
        std::swap(a, b);                //  swap ptrs
    }
    delete[] b;
    return(a);
}

Since your values are ints in the range 11 of 0 ... 1,000,000

You can create a int array 10 of of size 1,000,001, and do the whole thing 9 in two passes

Init the second array to all 8 zeros.

Make a pass through your input array, and 7 use the value as a subscript to increment 6 the value in the second array.

Once you do 5 that then the second pass is easy. walk 4 through the second array, and each element 3 tells you how many times that number appeared 2 in the original array. Use that information 1 to repopulate your input array.