Stable radix sort in-place using O(1) space

Question

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 <iostream>
#include <vector>
#include <cstring>

using namespace std;

void radix_sort(vector<int>& v) {
    //search for maximum number
    int max_number = v[0];
    for(int i = 1;i<v.size();i++) {
        if(max_number < 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 > 0) {           
        memset(bucket, 0, 10 * sizeof(int));        
        memset(bucket_max_index, 0, 10 * sizeof(int));      
        for(int i=0;i<v.size();i++) {
            bucket[(v[i] / exp) % 10]++;                        
        }       

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

        index = 0;
        vector<int> 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:

1. Is this O(kn) time ? (with k as the maximum number of digits)

2. Can we improve the above code to be a stable radix sort with O(1) space ?

Answer 1

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.