title: Inductive Proof of Counting Sort?
body: <p>I am covering the counting sort algorithm, and I understand how it works, but I would like to know if there is a specific way to prove that counting sort is a stable algorithm. I have an idea on how to inductively prove this, but I am unsure of how to do it.</p>
  
  <pre><code>for i = 1 to k
      C[i] = 0
  
  for j = 1 to n
     C[A[j]] = C[A[i]] + 1
  
  for i = 2 to k
     C[i] = C[i] + C[i-1]
  
  for j=n to 1
     B[C[A[j]]] = A[j]
     C[A[j]]--
  </code></pre>
  
  <p>I assume that the proof would start with a base case where an array has only one element</p>
  
  <p><strong>base case</strong> of n = 1, unsorted array A[1] = a1 , sorted array B[1] = a1</p>
  
  <p><strong>Inductive step:</strong> ???
  I'm not sure how to handle this type of inductive proof.</p>