title: Is counting sort in place & stable or not?
body: <p>As the question says , I want to confirm whether counting sort algorithm is in-place sorting algorithm or not.</p>
  
  <p>Wikipedia describes <a href="http://en.wikipedia.org/wiki/In-place_algorithm" rel="nofollow">in-place algorithm</a> as </p>
  
  <blockquote>
    <p>In computer science, an in-place algorithm (or in Latin in situ) is an algorithm which transforms input using a data structure with a small, constant amount of extra storage space. The input is usually overwritten by the output as the algorithm executes. An algorithm which is not in-place is sometimes called not-in-place or out-of-place (or ex situ in Latin).</p>
    
    <p>Stable sorting algorithms maintain the relative order of records with equal keys (i.e. values). That is, a sorting algorithm is stable if whenever there are two records R and S with the same key and with R appearing before S in the original list, R will appear before S in the sorted list.</p>
  </blockquote>
  
  <p>and also somewhere below counting sort page :</p>
  
  <blockquote>
    <p>As described, counting sort is not an in-place algorithm; even disregarding the count array, it needs separate input and output arrays.</p>
  </blockquote>
  
  <p>if we assume counting sort algorithm as :</p>
  
  <pre><code>countsort(){
      for i = 0 .... n  //where n is size of input array arr[]
          countArr[ arr[i] ] += 1
      //and then traverse countArr[] and rewrite arr[] with sorted values where value&gt;0
  </code></pre>
  
  <p>then how come is this not a stable and in place sort?</p>
  
  <p>Lets say input <code>key data</code> is represented by <code>numerals</code> and <code>satellite data</code> by characters , then for following data:</p>
  
  <pre><code>arr[] = { 1a,1b,1c,2z,5c,6c,7e,8q }  // keeping in mind only keys are sorted
  </code></pre>
  
  <p>wouldn't this algo traverse 1a then 1b then 1c and rewrite them in that very order? And also same array is being overwritten , so we just need a constant space depending upon type of keys rather than number of keys.</p>
  
  <p>Thanks.</p>