import java.util.*;

public class Counting_sort {

public static ArrayList<Integer> sort(ArrayList<Integer> arr) {

int maxValue = Collections.max(arr);

int minValue = Collections.min(arr);

ArrayList<Integer> count = new ArrayList<>(Collections.nCopies(maxValue - minValue + 1, 0));

for(int num : arr){

int j = num - minValue;

count.set(j, count.get(j) + 1);

}

ArrayList<Integer> SortedArr = new ArrayList<>();

// Build the sorted array from count array

//int totalvalue = minValue + maxValue;

for (int i = minValue; i <= maxValue; i++) {

while (count.get(i -minValue) > 0) {

SortedArr.add(i + minValue);

count.set(i - minValue, count.get(i - minValue) - 1);

}

}

return SortedArr;

}

}