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 
#include 
#include 

using namespace std;

void radix_sort(vector& v) {
    //search for maximum number
    int max_number = v[0];
    for(int i = 1;i 0) {           
        memset(bucket, 0, 10 * sizeof(int));        
        memset(bucket_max_index, 0, 10 * sizeof(int));      
        for(int i=0;i=0;i--) {
            index -= bucket[i];
            bucket_max_index[i] = index + bucket[i];
            bucket[i] = index;                      
        }   

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

        for(int i=0;i<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.

StackExchange Code Review Q#23999, answer score: 3