# MSD( Most significant digit ) Radix Sort

#include #include using namespace std;struct node { vector arr; struct node* nxt[10];};struct node* new_node(void){ struct node* tempNode = new node; for (int i = 0; i < 10; i++) { tempNode->nxt[i] = NULL; } return tempNode;}void msd_sort(struct node* root, int exp, vector& sorted_arr){ if (exp arr.size(); i++) { j = (root->arr[i] / exp) % 10; if (root->nxt[j] == NULL) { root->nxt[j] = new_node(); } root->nxt[j]->arr.push_back( root->arr[i]); } for (int i = 0; i < 10; i++) { if (root->nxt[i] != NULL) { if (root->nxt[i]->arr.size() > 1) { msd_sort(root->nxt[i], exp / 10, sorted_arr); } else { sorted_arr.push_back( root->nxt[i]->arr[0]); } } }}int get_max_exp(vector arr){ int mx = arr[0]; for (int i = 1; i < arr.size(); i++) { if (arr[i] > mx) { mx = arr[i]; } } int exp = 1; while (mx > 10) { mx /= 10; exp *= 10; } return exp;}void print(vector arr){ for (int i = 0; i < arr.size(); i++) cout arr); vector sorted_arr; msd_sort(root, exp, sorted_arr); cout