Counting Sort

Counting sort is a linear time sorting algorithm.

The principle of counting sort is to use an additional array C, where the i-th element is the number of elements whose value is equal to i in the array A to be sorted, and then arrange the elements in A to the correct position according to the array C.

Its process is divided into three steps:

1. 1. Count how many times each number appears;

   2. Find the prefix sum of the number of occurrences of each number;

   3. Using the prefix sum of the number of occurrences, calculate the ranking of each number from right to left.

Reasons for calculating prefix sums

Directly placing the elements corresponding to the positive numbers in C into A one after another cannot solve the problem of repeated elements.

We can determine a unique ranking for repeated elements by calculating the prefix sum for each item in the additional array C, combined with the numerical value of each item.

The value of each item in the additional array C is the number of repeated elements under the key value, and the prefix sum of the item is the ranking of the last repeated element.

If arranged in the reverse order of A, then obviously the sorted array will maintain the original order of A (with the same key value), that is, a stable sorting algorithm is obtained.