1/3/26, 3:58 PM DSA Counting Sort with Python
Tutorials References Exercises Sign In
HTML
CSS JAVASCRIPT SQL PYTHON JAVA PHP HOW TO [Link] C
DSA Counting Sort with Python
❮ Previous Next ❯
Counting Sort
The Counting Sort algorithm sorts an array by counting the number of times each value
occurs.
Sort
0 0 0 0 0
1 2 3 4 5
Run the simulation to see how 17 integer values from 1 till 5 are sorted using Counting Sort.
Counting Sort does not compare values like the previous sorting algorithms we have looked
at, and only works on non negative integers.
Furthermore, Counting Sort is fast when the range of possible values k is smaller than the
number of values n.
[Link] 1/9
1/3/26, 3:58 PM DSA Counting Sort with Python
Tutorials References Exercises Sign In
How it works:
HTML
CSS JAVASCRIPT SQL PYTHON JAVA PHP HOW TO [Link] C
1. Create a new array for counting how many there are of the different values.
2. Go through the array that needs to be sorted.
3. For each value, count it by increasing the counting array at the corresponding index.
4. After counting the values, go through the counting array to create the sorted array.
5. For each count in the counting array, create the correct number of elements, with
values that correspond to the counting array index.
Conditions for Counting Sort
These are the reasons why Counting Sort is said to only work for a limited range of non-
negative integer values:
Integer values: Counting Sort relies on counting occurrences of distinct values, so
they must be integers. With integers, each value fits with an index (for non negative
values), and there is a limited number of different values, so that the number of
possible different values k is not too big compared to the number of values n.
Non negative values: Counting Sort is usually implemented by creating an array for
counting. When the algorithm goes through the values to be sorted, value x is counted
by increasing the counting array value at index x. If we tried sorting negative values, we
would get in trouble with sorting value -3, because index -3 would be outside the
counting array.
Limited range of values: If the number of possible different values to be sorted k is
larger than the number of values to be sorted n, the counting array we need for
sorting will be larger than the original array we have that needs sorting, and the
algorithm becomes ineffective.
Manual Run Through
Before we implement the Counting Sort algorithm in a programming language, let's
manually run through a short array, just to get the idea.
Step 1: We start with an unsorted array.
myArray = [ 2, 3, 0, 2, 3, 2]
[Link] 2/9
1/3/26, 3:58 PM DSA Counting Sort with Python
Tutorials
Step 2: We References
create another Exercises
counting
array for how Sign In
many there are of each value. The array
has 4 elements, to hold values 0 through 3.
HTML
CSS JAVASCRIPT SQL PYTHON JAVA PHP HOW TO [Link] C
myArray = [ 2, 3, 0, 2, 3, 2]
countArray = [ 0, 0, 0, 0]
Step 3: Now let's start counting. The first element is 2, so we must increment the counting
array element at index 2.
myArray = [ 2, 3, 0, 2, 3, 2]
countArray = [ 0, 0, 1, 0]
Step 4: After counting a value, we can remove it, and count the next value, which is 3.
myArray = [ 3, 0, 2, 3, 2]
countArray = [ 0, 0, 1, 1]
Step 5: The next value we count is 0, so we increment index 0 in the counting array.
myArray = [ 0, 2, 3, 2]
countArray = [ 1, 0, 1, 1]
Step 6: We continue like this until all values are counted.
myArray = [ ]
countArray = [ 1, 0, 3, 2]
Step 7: Now we will recreate the elements from the initial array, and we will do it so that the
elements are ordered lowest to highest.
The first element in the counting array tells us that we have 1 element with value 0. So we
push 1 element with value 0 into the array, and we decrease the element at index 0 in the
counting array with 1.
myArray = [ 0]
countArray = [ 0, 0, 3, 2]
[Link] 3/9
1/3/26, 3:58 PM DSA Counting Sort with Python
Step 8: From the counting array we see that we do not need to create any elements with
value 1.
Tutorials References Exercises Sign In
HTML
CSS JAVASCRIPT SQL PYTHON JAVA PHP HOW TO [Link] C
myArray = [ 0]
countArray = [ 0, 0, 3, 2]
Step 9: We push 3 elements with value 2 into the end of the array. And as we create these
elements we also decrease the counting array at index 2.
myArray = [ 0, 2, 2, 2]
countArray = [ 0, 0, 0, 2]
Step 10: At last we must add 2 elements with value 3 at the end of the array.
myArray = [0, 2, 2, 2, 3, 3]
countArray = [ 0, 0, 0, 0]
Finally! The array is sorted.
Run the simulation below to see the steps above animated:
Sort
myArray = [ 2, 3, 0, 2, 3, 2 ]
countArray = [ 0, 0, 0, 0 ]
Implement Counting Sort in Python
To implement the Counting Sort algorithm in a Python program, we need:
1. An array with values to sort.
2. A 'countingSort' method that receives an array of integers.
3. An array inside the method to keep count of the values.
4. A loop inside the method that counts and removes values, by incrementing elements
in the counting array.
5. A loop inside the method that recreates the array by using the counting array, so that
the elements appear in the right order.
[Link] 4/9
1/3/26, 3:58 PM DSA Counting Sort with Python
One more thing: We need to find out what the highest value in the array is, so that the
Tutorials References Exercises Sign In
counting array can be created with the correct size. For example, if the highest value is 5, the
counting array must be 6 elements in total, to be able count all possible non negative
HTML
CSS JAVASCRIPT SQL PYTHON JAVA PHP HOW TO [Link] C
integers 0, 1, 2, 3, 4 and 5.
The resulting code looks like this:
Example Get your own Python Server
Using the Counting Sort algorithm in a Python program:
def countingSort(arr):
max_val = max(arr)
count = [0] * (max_val + 1)
while len(arr) > 0:
num = [Link](0)
count[num] += 1
for i in range(len(count)):
while count[i] > 0:
[Link](i)
count[i] -= 1
return arr
mylist = [4, 2, 2, 6, 3, 3, 1, 6, 5, 2, 3]
mysortedlist = countingSort(mylist)
print(mysortedlist)
Run Example »
Counting Sort Time Complexity
How fast the Counting Sort algorithm runs depends on both the range of possible values k
and the number of values n.
In general, time complexity for Counting Sort is O(n + k).
In a best case scenario, the range of possible different values k is very small compared to the
number of values n and Counting Sort has time complexity O(n).
[Link] 5/9
1/3/26, 3:58 PM DSA Counting Sort with Python
But in a worst case scenario, the range of possible different values k is very big compared to
Tutorials References Exercises
the number of values n and Counting Sort can have time complexity O(n ) or even worse.
Sign In
2
HTML
CSS JAVASCRIPT SQL PYTHON JAVA PHP HOW TO [Link] C
The plot below shows how much the time complexity for Counting Sort can vary.
As you can see, it is important to consider the range of values compared to the number of
values to be sorted before choosing Counting Sort as your algorithm. Also, as mentioned at
the top of the page, keep in mind that Counting Sort only works for non negative integer
values.
As mentioned previously: if the numbers to be sorted varies a lot in value (large k), and there
are few numbers to sort (small n), the Counting Sort algorithm is not effective.
If we hold n and k fixed, the "Random", "Descending" and "Ascending" alternatives in the
simulation above results in the same number of operations. This is because the same thing
happens in all three cases: A counting array is set up, the numbers are counted, and the new
sorted array is created.
❮ Previous Sign in to track progress Next ❯
[Link] 6/9
1/3/26, 3:58 PM DSA Counting Sort with Python
Tutorials References Exercises Sign In
HTML
CSS JAVASCRIPT SQL PYTHON JAVA PHP HOW TO [Link] C
COLOR PICKER
REMOVE ADS
Python - Output Variables with print() - [Link]
Click on ► to watch the video
[Link] 7/9
1/3/26, 3:58 PM DSA Counting Sort with Python
Tutorials References Exercises Sign In
HTML
CSS JAVASCRIPT SQL PYTHON JAVA PHP HOW TO [Link] C
-->
PLUS SPACES
GET CERTIFIED FOR TEACHERS
FOR BUSINESS CONTACT US
Top Tutorials
[Link] 8/9
1/3/26, 3:58 PM DSA Counting Sort with Python
HTML Tutorial
Tutorials CSS Tutorial
References
JavaScript Tutorial
Exercises Sign In
How To Tutorial
HTML
CSS SQL Tutorial SQL
JAVASCRIPT PYTHON JAVA PHP HOW TO [Link] C
Python Tutorial
[Link] Tutorial
Bootstrap Tutorial
PHP Tutorial
Java Tutorial
C++ Tutorial
jQuery Tutorial
Top References
HTML Reference
CSS Reference
JavaScript Reference
SQL Reference
Python Reference
[Link] Reference
Bootstrap Reference
PHP Reference
HTML Colors
Java Reference
AngularJS Reference
jQuery Reference
Top Examples Get Certified
HTML Examples HTML Certificate
CSS Examples CSS Certificate
JavaScript Examples JavaScript Certificate
How To Examples Front End Certificate
SQL Examples SQL Certificate
Python Examples Python Certificate
[Link] Examples PHP Certificate
Bootstrap Examples jQuery Certificate
PHP Examples Java Certificate
Java Examples C++ Certificate
XML Examples C# Certificate
jQuery Examples XML Certificate
FORUM ABOUT ACADEMY
W3Schools is optimized for learning and training. Examples might be simplified to improve reading and
learning.
Tutorials, references, and examples are constantly reviewed to avoid errors, but we cannot warrant full
correctness
of all content. While using W3Schools, you agree to have read and accepted our terms of use, cookies
and privacy policy.
Copyright 1999-2026 by Refsnes Data. All Rights Reserved. W3Schools is Powered by [Link].
[Link] 9/9