Inductive Proof of Counting Sort?

Question

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.

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]]--

I assume that the proof would start with a base case where an array has only one element

base case of n = 1, unsorted array A[1] = a1 , sorted array B[1] = a1

Inductive step: ??? I'm not sure how to handle this type of inductive proof.

You have a typo in the second loop, C[A[i]] should be C[A[j]]. And I would use proof by contradiction. Given two elements x and y where y follows x in the original array. Assume that x follows y in the output array, and prove that leads to a contradiction. — user3386109

Patrick87 Patrick87 · Accepted Answer · 2018-10-10T19:54:25

To write a proof by mathematical induction that counting sort is a stable sort, you must do three things:

Choose a base case and show that your claim is true in the base case.
Assume that the claim is true for all problem instances of size up to and including some size k. This is strong induction but we might as well do it because it's one less thing to worry about.
Demonstrate how problem instances of the next higher size must preserve the truth of the claim.

Our base cases might as well be empty arrays and arrays of size one. Any sorting algorithm is trivially stable on these.

The induction hypothesis is similarly easy to state: counting sort is stable on all arrays of no more than k elements.

The inductive step is the tricky part. Consider an array of size k+1. This array has a largest, last element (of the elements that are largest by the sorting criteria, there is one that appears last in the array). Consider the array of size k obtained by removing this element from the array of size k+1 and shifting elements appearing to the right of it left to fill the gap. By the induction hypothesis, counting sort is stable on this array of size k. To prove that counting sort is stable on the array of size k+1 elements, we must therefore show only that counting sort cannot place the largest, last element before any elements of the same size. To see this is true, notice that when the output array B is being constructed, j assumes the values n, n-1, …, 1 in descending order, so of all the elements with the same value as our largest, last element, it will reach our element first. Because of this, it is guaranteed to place this element further to the right in B than it will place any other element with the same value since C[A[j]] is decremented, never incremented, in the loop constructing B.

Inductive Proof of Counting Sort?

1 Answers