public static List<Integer> countingSort(List<Integer> arr) {
  int[] freqArray = new int[100];
  List<Integer> sortedList = new ArrayList<>();
  for (int num : arr) {
    freqArray[num]++;
  }

  for (int i = 0; i < freqArray.length; i++) {
    for (int j = 0; j < freqArray[i]; j++) {
      sortedList.add(i);
    }
  }

  return sortedList;
}

vector<int> countingSort(vector<int> arr) {
    vector<int> result, count(100, 0);
    for(int i = 0; i < arr.size(); i++) count[arr[i]]++;
    for(int i = 0; i < 100; i++) result.resize(result.size() + count[i], i);
    return result;
}

def countingSort(arr):
    # Write your code here
    res=[0]*(max(arr)+1)
    s=[]
    for i in arr:
        res[i]+=1
    for i in range(len(res)):
        s.extend([i]*res[i])
    return s

int* countingSort(int arr_count, int* arr, int* result_count) {
    // Trouver la valeur maximale dans le tableau pour optimiser la taille de "result"
    int max_val = 0;
    for (int i = 0; i < arr_count; i++) {
        if (arr[i] > max_val) {
            max_val = arr[i];
        }
    }

    // Allouer de la mémoire pour le tableau de comptage
    int* result = (int*)calloc(max_val + 1, sizeof(int));
    if (result == NULL) {
        fprintf(stderr, "allocation failed\n");
        exit(EXIT_FAILURE);
    }

    // Remplir le tableau de comptage
    for (int i = 0; i < arr_count; i++) {
        result[arr[i]]++;
    }

    // Allouer de la mémoire pour le tableau trié
    int* sortedArray = (int*)malloc(arr_count * sizeof(int));
    if (sortedArray == NULL) {
        fprintf(stderr, "allocation failed\n");
        exit(EXIT_FAILURE);
    }

    // Remplir le tableau trié en fonction des occurrences
    int j = 0;
    for (int i = 0; i <= max_val; i++) {
        while (result[i] > 0) {
            sortedArray[j++] = i;
            result[i]--;
        }
    }

    *result_count = arr_count;
    free(result);
    return sortedArray;
}