Implementation of Counting Sort using C++
#include &lt;bits/stdc++.h&gt;



You normally shouldn't use this. It includes every standard library header. If you compile without precompiled headers, this would make your compilation time much greater. The recommended practice is to #include just what you need, and if you want to use a precompiled header as well, that's just fine.




class count_sort
{



It is a bit strange to use a class for sorting. That your sort function is in a class implies that there's state, which is unexpected. You could use a namespace.


  std::map&lt;int, int&gt; m;
  std::map&lt;int, int&gt;::iterator it;



This state can easily be moved inside the functions, to the smallest scope possible.




  void counting_sort(std::vector&lt;int&gt;&amp; a){



The name counting_sort is a bit redundant, seeing as it's a member function of a class called count_sort. You could use sort, or even operator(). Other than that, by taking std::vector&lt;int&gt;&amp; as a parameter, you make this sort function not very general. The way the parameters are usually taken for a sort function (in C++) is as an iterator range:

template &lt;typename Iter&gt;
void counting_sort(Iter begin, Iter end) {


If you don't want to use templates, that's fine, but keep in mind that they make it more general.

One other thing to note is that you never change the vector in this function. That's a sign that it should be taken by const&amp; rather than &amp;. However, the expected semantics of a function called sort is that it modifies its parameter so that, after the function is called, the parameter is sorted. It's unusual and unexpected to have to call another function to obtain the output.



For the actual implementation, you can make use of C++11's range-based for loops (aka for-each loops). This:


for(int i=0; i&lt;a.size(); i++)
{
 m[a[i]]++;
}



Becomes this:

// Read as "`for` each `int i` in `a`, ..."
for (int i : a) {
    m[i]++;
}




Putting together my suggestions, without templates, would look something like this:

namespace counting_sort {
    void sort(std::vector&lt;int&gt;&amp; vec) {
        std::map&lt;int, int&gt; count;

        for (int i : vec) {
            ++count[i];
        }

        // modify the parameter; write the values back out
        auto begin = vec.begin();
        for (const auto&amp; pair : count) {
            while (pair-&gt;second &gt; 0) {
                *begin = pair-&gt;first;
                ++begin;
                --pair-&gt;second;
            }
        }
    }
}