void countingSort(vector<int>& arr, int maxVal) { vector<int> counts(maxVal + 1); vector<int> sortedArr(arr.size()); // Contar la frecuencia de cada elemento for (int i = 0; i < arr.size(); i++) { counts[arr[i]]++; } // Calcular las posiciones de inicio para cada elemento for (int i = 1; i <= maxVal; i++) { counts[i] += counts[i-1]; } // Ordenar los elementos for (int i = arr.size() - 1; i >= 0; i--) { sortedArr[counts[arr[i]] - 1] = arr[i]; counts[arr[i]]--; } // Copiar los elementos ordenados al arreglo original for (int i = 0; i < arr.size(); i++) { arr[i] = sortedArr[i]; } }

O(n)