COUNTING-SORT is stable:

• It is known that a sorting algorithm is table, if any two elements with same value appear in the same order in sorted array, as they appear in the original array.

• COUNTING-SORT is stable, as the input order among equal elements in the input array is preserved in the sorted array. That is, the elements with same value appear in the same order as they appear the original array.

Proving that C OUNTING -S ORT is stable:

• The final for loop of COUNTING-SORT runs from A.length to 1 and after i is stored in B, C[i] is decreased by 1. Thus, if there are any two elements with same value in A, the element with higher index in A is appear after the element with lower index in A.

• For example, consider two equal elements in A, stored at indices i₁ and i_2, where i₁ < i₂ . That is, A[i₁] = A[i₂].

• If there are k number of elements less than or equal to A[i₁] or A[i₂]. That is, C[A[i₁]] or C[A[i₂]]=k.

• Now, the final for loop processes A[i₂] first. That is, A[i₂] is stored in B at index k and C[A[i₁]] is decreased by 1. That is, C[A[i₁]]=k-1.

• Later A[i₁] is stored in B at index k-1. Obviously, k-1 < k. Thus, A[i₁] and A[i₂] appear in the same order in B as they appear in A.

Since the COUNTING-SORT is preserving the order of the elements with the same value, COUNTING-SORT is stable.

Example:

Even after applying COUNTING-SORT, the order of A[1] and A[4] is same in B.

Assume there is an array that stores n integer values. The range of integers lies in between 0 to k. Consider the following algorithm to determine number of integer lies in any particular range a and b.

Count (A)

1. Declare two new arrays and.

2. Initialize all elements of B[] array with 0.

//Now, use for loop to make increment in C[] array counter respective to elements of // A array. It will take time to process n elements of A array.

3. forto A.length( )

4.

5.

//use for loop to store count up to j^th element of B[] array. It will take time to process k elements of B[] array.

6. forto k

7.

The above algorithm stores the count to any i^th element in C [] array. The 3^rd line of above algorithm uses for loop which takes time to process n elements of A array.

The 6^th line of above algorithm uses for loop which takes time to process k elements of B[] array.

Therefore, the total processing time taken by Count Algorithm is.

Now, use following formula to determine number of integer lies in any particular range a and b:

This computation requires only time after the pre-processing time taken by the Count algorithm.