 Counting sort is applicable when each input is known to belong to a particular set, "S", of possibilities.The algorithm runs in O(|"S"| + "n") time and O(|"S"|) memory where "n" is the length of the input.It works by creating an integer array of size |"S"| and using the "i"th bin to count the occurrences of the "i"th member of "S" in the input.