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 ?

• David Rodríguez - dribeas: What is the question, whether your implementation of the algorithm is correct? whether the asymptotic costs are the ones of algorithm?
• Ben Voigt: @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?"
• bysreg: @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)
• Loki Astari: @DavidRodríguez-dribeas: This is code review. You are supposed to read and comment on the codes design/maintainability anything else that is important.

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.

• bysreg: thanks for the answer. can you also answer the second part of the question ?
• 200_success: Wikipedia says radix sort uses O(k + n) space. I challenge you to do better than conventional wisdom. ☺
• bysreg: Well, I guess for now, stable radix sort uses O(k+n) space. You would have to lose the stable property to achieve the O(1) space.