Stable radix sort in-place using O(1) space I am trying to implement a stable radix sort in place with O(1) space. I've seen Wikipedia, and I notice the C implementation is using a temporary variable to hold the sorted value for each pass, and the section of "in-place" MSD radix sort implementation is quite confusing. 

I took the C code and tried to implement it in C++ for the stable in-place radix sort version: 

#include &lt;iostream&gt;
#include &lt;vector&gt;
#include &lt;cstring&gt;

using namespace std;

void radix_sort(vector&lt;int&gt;&amp; v) {
    //search for maximum number
    int max_number = v[0];
    for(int i = 1;i&lt;v.size();i++) {
        if(max_number &lt; v[i])
            max_number = v[i];
    }

    int bucket[10]; // store first index for that digit
    int bucket_max_index[10]; // store maximum index for that digit 
    int exp = 1;

    while(max_number / exp &gt; 0) {           
        memset(bucket, 0, 10 * sizeof(int));        
        memset(bucket_max_index, 0, 10 * sizeof(int));      
        for(int i=0;i&lt;v.size();i++) {
            bucket[(v[i] / exp) % 10]++;                        
        }       

        int index = v.size();
        for(int i=9;i&gt;=0;i--) {
            index -= bucket[i];
            bucket_max_index[i] = index + bucket[i];
            bucket[i] = index;                      
        }   

        index = 0;
        vector&lt;int&gt; temp(v.size());
        for(int i=0;i&lt;v.size();i++) {
            int digit = (v[i] / exp) % 10;  
            temp[bucket[digit]] = v[i];         
            bucket[digit]++;
        }

        for(int i=0;i&lt;v.size();i++) {
            v[i] = temp[i];
        }       

        exp *= 10;
    }
}


EDIT:

Thanks to the comments, I checked and found out that I made a mistake. The original idea of the question is that I want to implement a stable in-place radix sort. 

I thought I succeeded in implementing it when I tested it with a several test cases (one of them is this test case: {1, 3, 2, 5, 8, 2, 3, 1}) .

I changed the code to a stable radix sort with O(n) space and changed my questions to:  


Is this O(kn) time ?  (with k as the maximum number of digits)
Can we improve the above code to be a stable radix sort with O(1) space ?
Yes, your radix sort appears to be correct, and runs in O(k n) time.

bucket_max_index is written to, but otherwise never used.  You can eliminate it completely.

Before the creation of the temp vector, you set index = 0.  It would be clearer to change that to assert(index == 0), since that should have been the result of v.size() - Σ bucket[i] in the previous loop.