1/3/26, 11:31 AM DSA Counting Sort with Python

❯
 Tutorials  References  Exercises  Certificates  Search... Upgrade Get Certified Sign In

HTML CSS JAVASCRIPT SQL PYTHON JAVA PHP HOW TO [Link] C C++ C# BOOTSTRAP REACT MYS
Binary Trees
Binary Search Trees
AVL Trees
Graphs
Linear Search
Binary Search
Bubble Sort
Selection Sort
Insertion Sort
Quick Sort
Counting Sort
Radix Sort
Merge Sort
DSA Counting Sort with Python
Python MySQL COLOR
❮ Previous Next ❯
MySQL Get Started PICKER
MySQL Create Database
MySQL Create Table
MySQL Insert Counting Sort
MySQL Select
MySQL Where 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.

How it works:

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.

[Link] 1/6
1/3/26, 11:31 AM DSA Counting Sort with Python

Conditions for Counting Sort

❯
 Tutorials  References Exercises  Certificates  Upgrade Get Certified Sign In

HTML CSS JAVASCRIPT SQL PYTHON JAVA PHP HOW TO [Link] C C++ C# BOOTSTRAP REACT MYS
These are the reasons why Counting Sort is said to only work for a limited range of non-
Binary Trees
negative integer values:
Binary Search Trees
AVL Trees Integer values: Counting Sort relies on counting occurrences of distinct values, so
Graphs they must be integers. With integers, each value fits with an index (for non negative
Linear Search values), and there is a limited number of different values, so that the number of
Binary Search possible different values k is not too big compared to the number of values n.
Bubble Sort Non negative values: Counting Sort is usually implemented by creating an array for
Selection Sort counting. When the algorithm goes through the values to be sorted, value x is
Insertion Sort counted by increasing the counting array value at index x. If we tried sorting negative
Quick Sort
values, we would get in trouble with sorting value -3, because index -3 would be
outside the counting array.
Counting Sort
Limited range of values: If the number of possible different values to be sorted k is
Radix Sort
larger than the number of values to be sorted n, the counting array we need for
Merge Sort
sorting will be larger than the original array we have that needs sorting, and the
algorithm becomes ineffective.
Python MySQL
MySQL Get Started
MySQL Create Database
MySQL Create Table
Manual Run Through
MySQL Insert
Before we implement the Counting Sort algorithm in a programming language, let's
MySQL Select
manually run through a short array, just to get the idea.
MySQL Where
Step 1: We start with an unsorted array.

myArray = [ 2, 3, 0, 2, 3, 2]

Step 2: We create another array for counting how many there are of each value. The array
has 4 elements, to hold values 0 through 3.

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.

[Link] 2/6
1/3/26, 11:31 AM DSA Counting Sort with Python

❯
 Tutorials 
myArray = [ ]
References  Exercises  Certificates 
countArray = [ 1, 0, 3, 2]
Upgrade Get Certified Sign In

HTML CSS JAVASCRIPT SQL PYTHON JAVA PHP HOW TO [Link] C C++ C# BOOTSTRAP REACT MYS
Binary Trees
Binary Search Trees Step 7: Now we will recreate the elements from the initial array, and we will do it so that
AVL Trees the elements are ordered lowest to highest.
Graphs
The first element in the counting array tells us that we have 1 element with value 0. So we
Linear Search
push 1 element with value 0 into the array, and we decrease the element at index 0 in the
Binary Search
counting array with 1.
Bubble Sort
Selection Sort myArray = [ 0]
Insertion Sort countArray = [ 0, 0, 3, 2]
Quick Sort
Counting Sort
Radix Sort Step 8: From the counting array we see that we do not need to create any elements with
Merge Sort value 1.

Python MySQL myArray = [ 0]

countArray = [ 0, 0, 3, 2]
MySQL Get Started
MySQL Create Database
MySQL Create Table
Step 9: We push 3 elements with value 2 into the end of the array. And as we create these
MySQL Insert
elements we also decrease the counting array at index 2.
MySQL Select
MySQL Where
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] 3/6
1/3/26, 11:31 AM 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  Certificates  Upgrade Get Certified
counting array can be created with the correct size. For example, if the highest value is 5,
Sign In

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 C++ C# BOOTSTRAP REACT MYS
Binary Trees
integers 0, 1, 2, 3, 4 and 5.

Binary Search Trees

The resulting code looks like this:
AVL Trees
Graphs
Linear Search
Example Get your own Python Server
Binary Search
Bubble Sort Using the Counting Sort algorithm in a Python program:
Selection Sort
Insertion Sort def countingSort(arr):
max_val = max(arr)
Quick Sort
count = [0] * (max_val + 1)
Counting Sort
Radix Sort
while len(arr) > 0:
Merge Sort num = [Link](0)
count[num] += 1
Python MySQL
for i in range(len(count)):
MySQL Get Started
while count[i] > 0:
MySQL Create Database
[Link](i)
MySQL Create Table
count[i] -= 1
MySQL Insert
MySQL Select return arr
MySQL Where
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).

But in a worst case scenario, the range of possible different values k is very big compared
to the number of values n and Counting Sort can have time complexity O(n ) or even
2

worse.

The plot below shows how much the time complexity for Counting Sort can vary.

[Link] 4/6
1/3/26, 11:31 AM DSA Counting Sort with Python

❯
 Tutorials  References  Exercises  Certificates  Upgrade Get Certified Sign In

HTML CSS JAVASCRIPT SQL PYTHON JAVA PHP HOW TO [Link] C C++ C# BOOTSTRAP REACT MYS
Binary Trees
Binary Search Trees
AVL Trees
Graphs
Linear Search
Binary Search
Bubble Sort
Selection Sort
Insertion Sort
Quick Sort
Counting Sort
Radix Sort
Merge Sort 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
Python MySQL at the top of the page, keep in mind that Counting Sort only works for non negative
MySQL Get Started integer values.
MySQL Create Database
As mentioned previously: if the numbers to be sorted varies a lot in value (large k), and
MySQL Create Table
there are few numbers to sort (small n), the Counting Sort algorithm is not effective.
MySQL Insert
MySQL Select If we hold n and k fixed, the "Random", "Descending" and "Ascending" alternatives in the
MySQL Where 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 ❯

-->
 PLUS SPACES GET CERTIFIED FOR TEACHERS

FOR BUSINESS CONTACT US

Top Tutorials Top References

HTML Tutorial HTML Reference
CSS Tutorial CSS Reference
JavaScript Tutorial JavaScript Reference
How To Tutorial SQL Reference
SQL Tutorial Python Reference
Python Tutorial [Link] Reference
[Link] Tutorial Bootstrap Reference
Bootstrap Tutorial PHP Reference
PHP Tutorial HTML Colors
Java Tutorial Java Reference
C++ Tutorial AngularJS Reference
jQuery Tutorial jQuery Reference

[Link] 5/6
1/3/26, 11:31 AM DSA Counting Sort with Python

Top Examples Get Certified ❯

 Tutorials  References  Exercises  Certificates  Upgrade Get Certified Sign In
HTML Examples HTML Certificate
HTML CSS CSS Examples SQL
JAVASCRIPT PYTHON JAVA PHP CSSHOW
Certificate
TO [Link] C C++ C# BOOTSTRAP REACT MYS
JavaScript Examples JavaScript Certificate
Binary Trees How To Examples Front End Certificate
SQL Examples SQL Certificate
Binary Search Trees
Python Examples Python Certificate
AVL Trees [Link] Examples PHP Certificate
Bootstrap Examples jQuery Certificate
Graphs PHP Examples Java Certificate
Java Examples C++ Certificate
Linear Search XML Examples C# Certificate
Binary Search jQuery Examples XML Certificate

Bubble Sort
Selection Sort
Insertion Sort      FORUM ABOUT ACADEMY
Quick Sort
W3Schools is optimized for learning and training. Examples might be simplified to improve reading and learning.
Counting Sort 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.
Radix Sort
Copyright 1999-2026 by Refsnes Data. All Rights Reserved. W3Schools is Powered by [Link].
Merge Sort

Python MySQL
MySQL Get Started
MySQL Create Database
MySQL Create Table
MySQL Insert
MySQL Select
MySQL Where

[Link] 6/6