Counting Sort

DSA · Sorting Algorithms

Theory

Counting sort does not compare elements. It counts how many times each value occurs in a known small range, then rebuilds the sorted output from those counts. It runs in O(n + k) time, where k is the range of values, which beats O(n log n) when k is small.

Why we use it

It sorts integers with a small range in linear time.

When to use it

Use it for ages, exam marks (0-100), ratings, or any integers with a limited range. Avoid it when values are spread over a huge range.

How it works

  1. Find max value k
  2. Create count array of size k + 1
  3. For each value x: count[x] += 1
  4. For v = 0..k: output v, count[v] times
  5. Sorted output in O(n + k)

Syntax

count = [0] * (max+1)
for x in arr: count[x] += 1
rebuild: for v, c in enumerate(count): output c copies of v

Time: O(n + k)   Space: O(k)   Stable version possible

Example

def counting_sort(arr):
    if not arr:
        return arr
    count = [0] * (max(arr) + 1)
    for x in arr:
        count[x] += 1
    result = []
    for value in range(len(count)):
        result += [value] * count[value]
    return result

marks = [4, 2, 2, 8, 3, 3, 1, 9, 4]
print(counting_sort(marks))

Key points

DSA topics

Introduction to DSA

Arrays and Searching

Sorting Algorithms

Linked Lists

Stacks and Queues

Hashing

Trees

Heaps

Graphs

Algorithm Techniques

Classic Algorithms

Dynamic Programming

T
Tech Town
Log InSign Up Free
Home SQL Python DSA Power BI Snowflake Databricks Spark Gen AI Practice Problems Contest Blog

Data Structures & Algorithms

The complete DSA roadmap: theory, why and when to use every structure and algorithm, Big O complexity, and Python code you can run right here in the browser.

{{ sectionCount }}
Sections
{{ topicCount }}
Topics
Free
Forever
Hands-on practice Practice DSA Online 251 problems across 13 patterns, with hidden tests and step-by-step optimal solutions. Start practising →
Section {{ sec.num }}

{{ sec.label }}

DSA  /  {{ current.sectionLabel }}  /  {{ current.name }}

{{ current.name }}

Theory

{{ current.def }}

Why we use it

{{ current.why }}

When to use it

{{ current.when }}

Flowchart — how {{ current.name }} works
{{ nd.text }}
{{ nd.text }}
◇ {{ nd.text }}
Yes → {{ nd.yes }}
No → {{ nd.no }}
Step-by-step visualisation
{{ cell.v }}
{{ cell.i }} {{ cell.tag }}
Step {{ vizStepLabel }}: {{ vizNote }}
■ comparing ■ swapping / moving ■ done / found ■ out of range
Complexity & Pseudocode
{{ current.syntax }}
Example Code
{{ current.example }}
▶ Try It Live — runs real Python 3 in your browser (first run loads the engine)
{{ liveOutput }}
{{ liveError }}
Key Points — click to check off as you learn
  • {{ pt.mark }} {{ pt.text }}

Share this topic