What is Counting Sort?

Counting Sort is a DSA lesson that explains counting sort in Python. A non-comparison sort that tallies how many times each value occurs — O(n + k) for small integer ranges. Copy the samples and run them in the Python editor. It is written for beginners who want a clear definition and working examples.

Should I run counting sort examples locally for better learning?

Yes. Use the browser editor on StudyGrid for a quick check, then Download the example and run it on your computer. Local runs show real errors and the real toolchain, which is one of the fastest ways to learn counting sort in this DSA Python lesson (Counting Sort).

How do I use counting sort in Python?

To use counting sort in Python, follow the examples on this StudyGrid page. Copy a snippet, run it in the browser, then Download and run it locally for better learning. Change the values and compare the output.

What is the syntax of counting sort?

This Counting Sort tutorial shows counting sort syntax with short Python examples. Use the code blocks in this lesson for the exact statements, then try them in your editor.

Counting Sort example for beginners

Yes. This page includes a beginner counting sort example you can copy and run. It is designed for searches such as "counting sort for beginners", "counting sort example", and "how to use counting sort".

What are common mistakes with counting sort?

Common counting sort mistakes include wrong syntax, mixing types, and skipping practice. Work through this DSA chapter in order, run every example, and check the output before moving on.

Why should I learn counting sort?

Counting Sort is used in real Python work. Learning counting sort helps you write clearer programs and continue the DSA tutorial on StudyGrid.

Is Counting Sort free to learn online?

Yes. You can learn counting sort free on StudyGrid (studygrid.in). This chapter is part of the DSA path and includes examples, syntax, and next-step links.

Python Tutorial

Counting Sort

A non-comparison sort that tallies how many times each value occurs — O(n + k) for small integer ranges.

← Quick Sort Radix Sort →

Sorting Without Comparisons

Comparison sorts cannot beat O(n log n). Counting sort sidesteps that limit: instead of comparing elements, it counts how many times each value appears, then reconstructs the sorted output from those counts. For n integers in the range 0..k it runs in O(n + k) — linear when k is small.

Implementation

def counting_sort(arr):
    if not arr:
        return arr
    max_val = max(arr)
    counts = [0] * (max_val + 1)

    for x in arr:                 # tally occurrences  -> O(n)
        counts[x] += 1

    result = []
    for value, freq in enumerate(counts):   # rebuild  -> O(n + k)
        result.extend([value] * freq)
    return result

print(counting_sort([4, 2, 2, 8, 3, 3, 1]))
# [1, 2, 2, 3, 3, 4, 8]

Stable Version with Prefix Sums

To keep counting sort stable (needed when it is a subroutine of radix sort), turn counts into cumulative positions and place elements from right to left.

def counting_sort_stable(arr):
    if not arr:
        return arr
    k = max(arr)
    counts = [0] * (k + 1)
    for x in arr:
        counts[x] += 1

    for i in range(1, k + 1):     # prefix sums -> final positions
        counts[i] += counts[i - 1]

    output = [0] * len(arr)
    for x in reversed(arr):       # right-to-left keeps it stable
        counts[x] -= 1
        output[counts[x]] = x
    return output

print(counting_sort_stable([4, 2, 2, 8, 3, 3, 1]))

When to Use It

Metric	Value
Time	O(n + k)
Space	O(n + k)
Stable?	Yes (prefix-sum version)
Works on	Integers / small discrete keys only

Counting sort is efficient only when the value range k is not much larger than n. Sorting a few numbers spanning 0..1,000,000 would allocate a million-slot array — use quicksort or radix sort instead.

Handling Negative Numbers

def counting_sort_signed(arr):
    lo, hi = min(arr), max(arr)
    counts = [0] * (hi - lo + 1)
    for x in arr:
        counts[x - lo] += 1        # shift by lo so index >= 0
    out = []
    for i, freq in enumerate(counts):
        out.extend([i + lo] * freq)
    return out

print(counting_sort_signed([-2, 3, -1, 0, 3]))
# [-2, -1, 0, 3, 3]

Best Practices

Use counting sort for integers/characters in a small, known range.
Use the stable prefix-sum version when it feeds radix sort or when duplicates carry extra data.
Shift by the minimum value to support negatives.
For large or unbounded ranges, prefer a comparison sort or radix sort.

Try It Yourself

Exercise 1: Why is counting sort a poor choice for values spanning 0 to 1,000,000 with only 10 numbers?

Show solution

It allocates a counts array sized to the range (k), so it would create a million-slot array to sort 10 values — hugely wasteful.

Exercise 2: Counting sort beats the O(n log n) comparison lower bound. How?

Show solution

It never compares elements — it counts occurrences by value, which sidesteps the comparison-based limit (but only works for small integer ranges).

📘 Real-World Deep Dive

Knowing <strong>DSA Counting Sort (algorithms & data structures)</strong> well is what turns algorithms & data structures from a curiosity into a daily tool — you'll reach for it in nearly every real project.

Real-Life Scenario

An end-to-end usage of DSA Counting Sort that you'd actually see in a data pipeline or analytics notebook.

Real-Life Example

def counting(xs, k):
    counts = [0] * (k + 1)
    for x in xs: counts[x] += 1
    out = []
    for v, c in enumerate(counts):
        out.extend([v] * c)
    return out

print(counting([4, 2, 2, 8, 3, 3, 1], k=8))

Expected Output

(see source)

Common mistakes

Off-by-one errors in binary-search: the standard idiom is while lo <= hi with mid = (lo + hi) // 2.
Recursive algorithms blow the stack for n > ~10⁴; convert to iterative with an explicit stack.
Comparison algorithms (sorted(iterable)) are stable by default in Python — surprising for Java/C++ users.
Treating DSA Counting Sort as a black box without reading the docs — the API has subtle defaults that bite when you scale.

🚀 Performance & Best Practices

Use bisect.bisect_left / bisect_right instead of writing your own binary search.
Convert a sorted search into a tuple-access pattern with numpy.searchsorted for huge arrays.
Use heapq for priority queues instead of maintaining a sorted list manually.
When working with algorithms & data structures, prefer vectorised / batched operations over Python loops.

🧪 Try It Yourself

Reproduce the snippet on a representative slice of your own data.
Profile the snippet with cProfile or timeit and find the single biggest improvement.
Generalise the snippet into a small, reusable function you can drop into future projects.