Radix Sort

• Time : O(n log10(max element))
• Space : O(n)

c++

#include <vector>
#include <queue>
using namespace std;

vector<int> radixSort(vector<int> array) {
	if(array.empty()) return {};
	int ma = log10(*max_element(begin(array), end(array))), p = 0, n = array.size();
	for(int i = 0; i <= ma; i++) {
		int d = pow(10, i);
		queue<int> q[10];
		for(int j = 0; j < n; j++) {
			int bucket = (int)(array[j] / d) % 10;
			q[bucket].push(array[j]);
		}
		for(int j = 0, idx = 0; j < 10; j++) {
			while(!q[j].empty()) {
				array[idx++] = q[j].front();
				q[j].pop();
			}
		}
	}
	return array;
}