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

using namespace std;

//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 ?

• What is the question, whether your implementation of the algorithm is correct? whether the asymptotic costs are the ones of algorithm? – David Rodríguez - dribeas Mar 17 '13 at 2:15
• @David: That's the way I understand it... "Does this code correctly sort inputs?" and "Is the stable radix sort algorithm (which implies its memory and runtime complexity) implemented by this code?" – Ben Voigt Mar 17 '13 at 2:43
• @DavidRodríguez-dribeas yes, i was asking if this code is correct and whether the time complexity is O(kn) and the space complexity is O(1) – bysreg Mar 17 '13 at 3:16
• @DavidRodríguez-dribeas: This is code review. You are supposed to read and comment on the codes design/maintainability anything else that is important. – Martin York Mar 18 '13 at 6:15

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.