Counting Sort

Counting Sort is a non-comparison-based sorting algorithm that works well when there is a limited range of input values. It is particularly efficient when the range of input values is small compared to the number of elements to be sorted. The basic idea behind Counting Sort is to count the frequency of each distinct element in the input array and use that information to place the elements in their correct sorted positions.

Algorithm:

  1. Find the range of the input array (minimum and maximum elements).
  2. Create a count array to store the count of each unique object.
  3. Store the count of each unique object in the count array.
  4. Modify the count array by storing the actual position of each object in the output array.
  5. Build the output array using the modified count array and the original input array.
  6. Copy the sorted elements into the original array.
2 5 4 6 1 3
Complexity
Time Complexity (Best, Average, Worst) O(n + k)
Space Complexity O(k)

Where n is the number of elements in the input array and k is the range of input.

Counting Sort Visualizer

Counting Sort Code


        


        

            
Practice Questions

            

                

                    Question Number
                    Question Title
                    Level
                    Link
                

                

                    1
                    Sort an Array
                    Easy
                    Link
                

                

                    2
                    Sort Characters By Frequency
                    Medium
                    Link
                

                

                    3
                    Largest Number
                    Hard
                    Link