public static List<Integer> countingSort(List<Integer> arr) {
        Collections.sort(arr); return arr;
    }

public static List<Integer> countingSort(List<Integer> arr) {
        
        int[] frequency = new int[100];
        List<Integer> sorted = new ArrayList<>();
        
        // count frequency
        for(int i = 0; i < arr.size(); i++) {
            frequency[arr.get(i)]++;
        }
        
        for(int i = 0; i < frequency.length; i++) {
            int count = frequency[i];
            
            if(count == 0) {
                continue;
            }
            
            for(int k = 0; k < count; k++) {
                sorted.add(i);
            }
            
        }
                     
        return sorted;
    }

void merge_sort(vector<int> &arr, int left, int right, int middle){
    int i=left,j=middle+1,temp_i=0;
    int temp[right-left+1];
    
    while(i<=middle && j<=right){
        if(arr[i]<arr[j])
            temp[temp_i++]=arr[i++];
        else
            temp[temp_i++]=arr[j++];
    }
    
    while(i<=middle)
        temp[temp_i++]=arr[i++];
    
    while(j<=right)
        temp[temp_i++]=arr[j++];
        
    temp_i=0;
    
    for(i=left;i<=right;i++){
        arr[i]=temp[temp_i++];
    }
    
}
void merge(vector<int> &arr, int left, int right){
    if(left<right){
        
        int middle = (right+left)/2;
        
        merge(arr, left, middle);
        merge(arr, middle+1, right);
        merge_sort(arr,left,right,middle);
    }
}

vector<int> countingSort(vector<int> arr) {
    merge(arr,0,arr.size()-1);
    return arr;
}