Counting Sort (Stable)

Stable sort means, relative order of the elements remains unchanged.

Example

Steps, we follow:

• Firstly, determine the range of the elements in the array by finding the minimum and maximum values. This range helps decide the size of the count array.
• Create the count array based on the calculated range and initialize all its values to zero. Then, traverse the original array and store the frequency of each element in the count array.
• Convert the count array into a prefix (cumulative) array by adding the current count with the previous one. This step helps in determining the correct position of each element in the sorted array.
• Build the sorted array by iterating over the original array, placing each element at its correct position using the prefix array, and then copying the sorted elements back to the original array.