Counting sort have time complexity: O(n+k) n-> size of input k-> abs. diff. b/w min and max value. In several cases counting sort is better than the comparison based sorting algorithm Is it present in std: sort in STL? if no, Is there any reason? Also any function for counting sort available in STL?
Is counting sort present in std: sort in STL?
No, It's not present. The sort function is based on quick sort and other heuristics.
if no, Is there any reason?
Probably because it's easy to implement. Check psuedocode
count = array of k+1 zeros
for x in input do
count[key(x)] += 1
total = 0
for i in 0, 1, ... k do
count[i], total = total, count[i] + total
output = array of the same length as input
for x in input do
output[count[key(x)]] = x
count[key(x)] += 1
return output
Also any function for counting sort available in STL?
C++ STL provides the basic fitting data structures - arrays and vector which can be used for implementing counting sort.
map can also be used to implement counting sort, but it won't be O(n) anymore, since map operations are O(logn) complexity.