How Counting Sort Works: Step-by-Step Guide

1. Introduction and Core Concepts

Counting sort is a non-comparison based sorting algorithm that excels when sorting integers or objects with integer keys within a relatively small range. Unlike comparison sorts such as quicksort, mergesort, or heapsort, which determine order by comparing elements pairwise, counting sort exploits the actual values of the elements to determine their positions directly. This fundamental difference allows it to break the Omega(n log n) lower bound that limits all comparison-based algorithms, achieving linear time performance when its preconditions are met.

At its heart, counting sort is an integer sorting algorithm based on counting the frequency of each distinct key value. Instead of shuffling elements around through comparisons and swaps, it creates an auxiliary counting array that tallies how many times each value appears in the input. By transforming these counts into cumulative positions, the algorithm can place each element directly into its final sorted location. This makes it exceptionally fast, predictable, and stable when implemented correctly.

Understanding counting sort matters for several reasons beyond its raw speed. First, it introduces the powerful idea of trading space for time — using extra memory to achieve faster computation. Second, it serves as a critical subroutine for more advanced linear-time algorithms like radix sort, which sorts multi-digit numbers by repeatedly applying counting sort to each digit position. Third, it illustrates a broader class of distribution-based sorts that are essential in systems programming, data engineering, and competitive programming where input constraints are known in advance.

Why Counting Sort Matters

Most general-purpose sorting algorithms make no assumptions about the data. Counting sort does, and that assumption is its strength. When you know your data consists of integers in a bounded range — for example, exam scores from 0 to 100, ages from 0 to 120, or bytes from 0 to 255 — counting sort can outperform even highly optimized quicksort implementations by a significant margin. Its deterministic O(n + k) time complexity, where k is the range of input, makes it ideal for real-time systems where worst-case guarantees are critical.

Counting sort is also inherently stable, meaning elements with equal keys retain their original relative order. This property is crucial when sorting complex records by a key while preserving secondary ordering, such as sorting students by grade while keeping alphabetical order within each grade. Stability also enables its use as a building block in radix sort, where stability across digit passes is required for correctness.

Key Assumptions and Preconditions

Counting sort is not a universal replacement for comparison sorts. It requires that the input consists of non-negative integers, or integers that can be mapped to a non-negative range, and that the range k is not significantly larger than the number of elements n. If k is enormous — for example, sorting just ten numbers in the range 0 to 1 billion — the auxiliary count array would be prohibitively large, negating any time advantage. Recognizing when these preconditions hold is the key to applying counting sort effectively.

2. How It Works

Counting sort operates in three distinct phases: counting, accumulating, and distributing. The algorithm does not compare elements to each other at any point. Instead, it counts occurrences, computes final positions, and then writes elements to a sorted output array. This three-phase structure makes it easy to understand, implement, and analyze, while also making its memory access patterns highly cache-friendly.

In the first phase, the algorithm scans the input array and builds a frequency histogram. If the input range is 0 to k, it allocates a count array C of size k+1, initialized to zeros. For each element x in the input, it increments C[x] by one. After this pass, C[v] contains exactly the number of times value v appears in the input. This phase runs in O(n) time and captures all the information needed to reconstruct the sorted order without any comparisons.

The second phase transforms the frequency counts into starting positions through a prefix sum, also called a cumulative sum. For each index i from 1 to k, it sets C[i] = C[i] + C[i-1]. After this transformation, C[i] represents the number of elements less than or equal to i, which is precisely the index of the last occurrence of i in the sorted output (using one-based indexing) or one past it (using zero-based indexing). This cumulative array effectively encodes the final destination for every distinct value.

The Three Phases in Detail

The final phase distributes elements into the output array in a stable manner. To maintain stability, the input is typically traversed in reverse order. For each element x, the algorithm looks up C[x], decrements it by one to obtain the correct zero-based index, and places x at output[C[x]]. Because equal elements are processed from last to first and placed from the end of their block backwards, their original relative order is preserved. This reverse traversal is the subtle detail that guarantees stability.

Consider an alternative simpler reconstruction for non-stable sorting: one could simply iterate over the count array and append value i exactly C[i] times to the output. This approach is easier to code and requires no prefix sum, but it loses stability and cannot be used to sort objects with satellite data. The stable prefix-sum version is more general and is the canonical form taught in algorithms textbooks.

Conceptually, counting sort can be viewed as a form of bucket sort where each bucket corresponds to a single integer value, or as a histogram sort. The count array is essentially a histogram of the input distribution, and the prefix sum converts that histogram into an index map. This viewpoint helps explain why the algorithm is so efficient for dense, narrow distributions and so inefficient for sparse, wide ones.

3. Implementation

Implementing counting sort in Python is straightforward, but handling edge cases such as empty inputs, negative numbers, and large ranges requires care. The following implementations progress from the simplest non-negative version to a fully general, stable, and optimized variant suitable for production use. All examples include detailed comments and handle Python-specific considerations like dynamic typing and memory allocation.

The basic version assumes all inputs are non-negative integers and that the maximum value is not excessively large. It demonstrates the core counting and reconstruction logic without the overhead of handling negatives or ensuring stability. This version is ideal for learning and for cases where you control the input domain, such as sorting pixel intensities or test scores.

def counting_sort_basic(arr):
    """
    Basic counting sort for non-negative integers.
    Not stable, but simple and memory efficient for small k.
    """
    if not arr:
        return arr

    # Find the range k - size of count array
    max_val = max(arr)
    
    # Count array of size max_val + 1, initialized to 0
    count = [0] * (max_val + 1)

    # Phase 1: Count frequencies
    for num in arr:
        count[num] += 1

    # Phase 2 & 3: Reconstruct sorted array in place
    # Simply iterate over count array and overwrite input
    idx = 0
    for value in range(len(count)):
        freq = count[value]
        for _ in range(freq):
            arr[idx] = value
            idx += 1
    return arr

# Example usage
# data = [4, 2, 2, 8, 3, 3, 1]
# counting_sort_basic(data)  # Returns [1, 2, 2, 3, 3, 4, 8]

To handle negative integers, we offset all values by the minimum element so that the smallest value maps to index zero. This technique preserves the linear time complexity while expanding applicability to any integer range. The offset is computed as -min_val, and the count array size becomes max_val - min_val + 1. Note that if the range is huge, this allocation will still be expensive, which is why range checks are important.

def counting_sort_with_negatives(arr):
    """
    Counting sort that handles negative integers via offset.
    Stable version using prefix sums and output array.
    """
    if not arr:
        return []

    min_val = min(arr)
    max_val = max(arr)
    k = max_val - min_val + 1  # Range size

    # Guard against excessively large range
    if k > 10**6 and len(arr) < k // 10:
        raise ValueError("Range k is too large relative to n; use comparison sort")

    count = [0] * k
    output = [0] * len(arr)

    # Phase 1: Count frequencies with offset
    for num in arr:
        count[num - min_val] += 1

    # Phase 2: Compute prefix sums (cumulative counts)
    for i in range(1, len(count)):
        count[i] += count[i - 1]

    # Phase 3: Place elements stably (traverse reversed)
    for num in reversed(arr):
        idx = num - min_val
        count[idx] -= 1
        output[count[idx]] = num

    return output

# Handles: [-5, -10, 0, -3, 8, 5, -1]
# Returns: [-10, -5, -3, -1, 0, 5, 8]

The stable implementation is essential when sorting objects or when counting sort is used as a subroutine in radix sort. Stability ensures that if two elements have the same key, their original order is preserved. This is achieved by processing the input array from right to left during the distribution phase, as shown above. Without this reverse traversal, the sort would still be correct but not stable.

def counting_sort_stable_objects(arr, key=lambda x: x):
    """
    Stable counting sort for objects using a key function.
    Sorts list of objects based on integer key.
    Example: sorting tuples (name, grade) by grade.
    """
    if not arr:
        return []

    # Extract keys and find range
    keys = [key(obj) for obj in arr]
    min_key = min(keys)
    max_key = max(keys)
    k = max_key - min_key + 1

    count = [0] * k
    output = [None] * len(arr)

    # Count frequencies of keys
    for k_val in keys:
        count[k_val - min_key] += 1

    # Cumulative counts
    for i in range(1, k):
        count[i] += count[i - 1]

    # Distribute objects stably
    for i in range(len(arr) - 1, -1, -1):
        k_val = keys[i]
        idx = k_val - min_key
        count[idx] -= 1
        output[count[idx]] = arr[i]

    return output

# Example: students = [("Alice", 85), ("Bob", 92), ("Charlie", 85)]
# counting_sort_stable_objects(students, key=lambda x: x[1])
# Keeps Alice before Charlie for grade 85 due to stability

An optimized version minimizes memory allocation and avoids unnecessary work when the range is sparse. It first checks whether counting sort is appropriate and falls back to Python's built-in Timsort if not. It also uses local variable binding for speed and handles the case where the input is already sorted or contains many duplicates efficiently. In performance-critical code, these micro-optimizations can yield measurable gains.

def counting_sort_optimized(arr):
    """
    Optimized counting sort with range check and early exits.
    Falls back to built-in sort if range is too large.
    """
    n = len(arr)
    if n <= 1:
        return arr[:]  # Already sorted

    min_val = min(arr)
    max_val = max(arr)
    k = max_val - min_val + 1

    # Heuristic: if k > 5*n, comparison sort is likely faster
    # This avoids huge count arrays for sparse data
    if k > 5 * n:
        # Fallback to Python's Timsort O(n log n)
        return sorted(arr)

    count = [0] * k
    for num in arr:
        count[num - min_val] += 1

    # Reconstruct without extra output array when stability not needed
    # Use write pointer for in-place reconstruction
    write_idx = 0
    for value_offset in range(k):
        freq = count[value_offset]
        if freq > 0:
            actual_value = value_offset + min_val
            for _ in range(freq):
                arr[write_idx] = actual_value
                write_idx += 1
    return arr

4. Step-by-Step Example

To make the abstract mechanism concrete, let us walk through counting sort on a small example array: A = [4, 2, 2, 8, 3, 3, 1]. The range is 0 to 8, so we will allocate a count array C of size 9 (indices 0 through 8). Although the minimum is 1, we include 0 for simplicity; its count will remain zero. This example illustrates every phase including the prefix sum and stable placement.

Phase 1 begins with C = [0, 0, 0, 0, 0, 0, 0, 0, 0]. We scan A from left to right. Encountering 4 increments C[4] to 1. Next, 2 increments C[2] to 1, then the second 2 increments C[2] to 2. Continuing, 8 makes C[8]=1, 3 makes C[3]=1, the next 3 makes C[3]=2, and finally 1 makes C[1]=1. After the full scan, C = [0, 1, 2, 2, 1, 0, 0, 0, 1]. This array tells us there is one 1, two 2s, two 3s, one 4, and one 8.

Phase 2 computes the prefix sum. We iterate i from 1 to 8, setting C[i] = C[i] + C[i-1]. Step by step: C[1] stays 1 (0+1), C[2] becomes 3 (1+2), C[3] becomes 5 (3+2), C[4] becomes 6 (5+1), C[5] stays 6 (6+0), C[6] stays 6, C[7] stays 6, and C[8] becomes 7 (6+1). The final cumulative array is C = [0, 1, 3, 5, 6, 6, 6, 6, 7]. Now C[v] indicates the position after the last occurrence of v in the sorted array using one-based indexing. For example, C[3]=5 means there are five elements less than or equal to 3.

Stable Distribution Walkthrough

Phase 3 distributes elements into output array B of size 7, initially empty. To ensure stability we traverse A in reverse: [1, 3, 3, 8, 2, 2, 4]. Process 1: C[1]=1, decrement to 0, place 1 at B[0] → B=[1, _, _, _, _, _, _]. Process 3 (the last 3): C[3]=5, decrement to 4, place 3 at B[4] → B=[1, _, _, _, 3, _, _]. Next 3: C[3]=4, decrement to 3, place 3 at B[3] → B=[1, _, _, 3, 3, _, _]. Next 8: C[8]=7, decrement to 6, place 8 at B[6] → B=[1, _, _, 3, 3, _, 8].

Continue with 2 (the second 2): C[2]=3, decrement to 2, place 2 at B[2] → B=[1, _, 2, 3, 3, _, 8]. Next 2 (the first 2): C[2]=2, decrement to 1, place 2 at B[1] → B=[1, 2, 2, 3, 3, _, 8]. Finally 4: C[4]=6, decrement to 5, place 4 at B[5] → B=[1, 2, 2, 3, 3, 4, 8]. The array is now sorted, and because we processed duplicates in reverse, the two 2s and two 3s retained their original relative order.

This walkthrough highlights why counting sort is so intuitive: it never compares 2 versus 3 directly, but instead uses counting to deduce that 2 must come before 3 because there are fewer elements less than or equal to 2 than there are less than or equal to 3. The prefix sum is the key insight that converts frequencies into positions, and the reverse traversal guarantees stability without extra cost.

5. Complexity Analysis

Counting sort's efficiency is best understood by analyzing each phase separately and then combining the results. Unlike comparison sorts where time depends solely on n, counting sort's time depends on both n (number of elements) and k (range of input values). This two-parameter complexity is what allows it to be linear in n when k is O(n), but also what makes it impractical when k dominates n.

The counting phase iterates over n elements and performs O(1) work per element, yielding O(n) time. The prefix sum phase iterates over k entries in the count array, yielding O(k) time. The distribution phase again iterates over n elements, yielding another O(n) time. Summing these gives overall time complexity O(n + k). Importantly, this bound holds for best, average, and worst cases — there is no input permutation that makes counting sort significantly faster or slower, because it does not depend on comparisons or pivot choices.

Space complexity is O(n + k) in the stable version, which requires both the count array of size k+1 and the output array of size n. The in-place unstable reconstruction variant can reduce this to O(k) auxiliary space by overwriting the input, but it sacrifices stability. In either case, the dominant factor is k; when k is small, memory usage is modest, but when k is large, memory can become the bottleneck long before time does.

Detailed Breakdown

Best case, average case, and worst case are identical for counting sort because its control flow does not depend on the input order. Whether the input is already sorted, reverse sorted, or random, the algorithm performs the same counting, prefix sum, and distribution steps. This predictability is a major advantage in hard real-time systems where worst-case execution time must be bounded and jitter must be minimized.

However, the hidden constant factors matter. Initializing a large count array of size k can be expensive due to memory allocation and cache misses, even if many entries remain zero. Python's list allocation of [0] * k is relatively fast, but for k in the millions, the initialization alone may dominate runtime. This is why the heuristic of checking whether k is much larger than n before proceeding is crucial in practice.

When k = O(n), counting sort achieves O(n) linear time, which is asymptotically optimal and strictly better than the Omega(n log n) lower bound for comparison sorts. When k = O(n log n), it still matches comparison sorts asymptotically, but with better constants for integer data. When k is much larger, such as k = Omega(n²), counting sort becomes O(k) and is no longer competitive. Understanding this tradeoff is essential for algorithm selection.

6. Variations and Optimizations

The classic counting sort can be adapted and optimized in numerous ways to handle broader inputs, reduce memory usage, or improve cache performance. These variations address the main limitations of the basic algorithm — its restriction to integers, its memory consumption for large ranges, and its inability to handle floating-point or string keys directly.

One common optimization is range compression. Instead of allocating k = max - min + 1 entries when the data is sparse, we can compress the range by sorting the distinct values or using a hash map for counting. This approach, sometimes called counting sort with coordinate compression, first collects distinct values, sorts them (using a comparison sort), maps each distinct value to a compressed index 0 to d-1 where d is the number of distinct values, then counts using the compressed indices. While this adds an O(d log d) step, it makes counting sort feasible when k is huge but d is small.

Another important variation is the use of counting sort as a subroutine in radix sort. Radix sort sorts integers digit by digit, from least significant to most significant, using a stable sort for each digit. Counting sort is the ideal stable sort for this purpose because each digit has a small range (0-9 for decimal, 0-255 for bytes). By applying counting sort repeatedly to each digit position, radix sort achieves O(d * (n + b)) time where d is the number of digits and b is the base, effectively sorting large integers in linear time.

Handling Special Cases

For sorting bytes or characters, counting sort can be highly optimized using fixed-size count arrays. Since a byte has only 256 possible values, the count array is always size 256, making the algorithm extremely fast and cache-friendly. This is why counting sort is often used in string sorting algorithms like MSD radix sort and in image processing where pixel values are 0-255. The fixed size also allows for stack allocation and SIMD optimizations in lower-level languages.

An in-place optimization avoids the output array by reconstructing the sorted sequence directly from the count array, as shown in the basic implementation. This reduces space to O(k) but loses stability. For many applications where stability is not required — such as sorting plain integers with no satellite data — this tradeoff is worthwhile. The in-place method also has better locality because it writes sequentially through the input array.

Parallel and vectorized variants exist for multi-core and GPU environments. The counting phase is embarrassingly parallel: the input can be partitioned across threads, each building a local histogram, which are then merged. The prefix sum can be parallelized using well-known parallel prefix algorithms. These parallelizations allow counting sort to scale to billions of elements on modern hardware, making it relevant for big data and scientific computing.

7. Real-World Applications

Despite its specialized preconditions, counting sort appears in a surprising number of real-world systems, often hidden inside larger algorithms or used for specific data types where its range assumptions hold naturally. Its predictable performance and linear time make it attractive in performance-critical infrastructure.

In web servers and databases, counting sort is used for sorting and ranking operations on bounded integer keys. For example, database query optimizers may use counting sort to sort intermediate results by small integer columns such as status codes, priority levels, or enumerated types. Web analytics platforms that count and sort page views, error codes, or HTTP status frequencies (which are limited to about 60 distinct codes) can use counting sort to generate histograms and sorted reports in linear time. In-memory databases like Redis use variants of counting sort for sorting sets with integer scores.

Operating systems and networking stacks use counting sort for packet classification and scheduling. Network routers classify packets by port numbers (0-65535) or DSCP values (0-63) and need to sort or prioritize them quickly. Counting sort's O(n + k) with small k is perfect here. Similarly, process schedulers that manage priorities in a limited range (e as in Unix nice values -20 to 19) can use counting sort to reorder run queues efficiently without the overhead of a general-purpose sort.

Domain-Specific Uses

Image processing and computer graphics rely heavily on counting sort. An 8-bit grayscale image has pixel values 0-255, and operations like histogram equalization, median filtering, and quantization require sorting or counting pixel intensities. Counting sort can sort all pixels in an image in O(n + 256) time, which is effectively O(n). This is used in real-time video processing, medical imaging, and computational photography where performance is critical.

Bioinformatics is another domain where counting sort shines. DNA sequences consist of only four nucleotides (A, C, G, T), and counting sort is used to sort k-mers, count nucleotide frequencies, and implement the Burrows-Wheeler transform for genome assembly. When sorting suffixes or building FM-indexes for large genomes, radix sort with counting sort as a subroutine is a standard technique due to its linear time and low memory overhead for small alphabets.

In education and data science, counting sort is used for sorting ages, grades, survey responses, and other bounded integer data. Any dataset where values fall into a small, known range — such as Likert scale responses (1-5), years (1900-2100), or counts of events — can benefit. Data engineers often use counting sort in ETL pipelines to sort and deduplicate such columns before loading into data warehouses, where it outperforms generic sorts by orders of magnitude for suitable data.

8. Comparison with Alternatives

Choosing a sorting algorithm requires understanding the tradeoffs between time complexity, space usage, stability, and assumptions about the data. Counting sort occupies a unique niche: it is the fastest option when its assumptions hold, but it is inapplicable when they do not. Comparing it to general-purpose and other non-comparison sorts clarifies when to use it and when to avoid it.

Comparison sorts like quicksort, mergesort, and heapsort make no assumptions about the data and work for any comparable type, including floats, strings, and objects. They all have Omega(n log n) lower bounds, but their constants and practical performance differ. Quicksort is usually fastest in practice due to cache locality and in-place partitioning, but it has O(n²) worst case and is not stable. Mergesort is stable and guarantees O(n log n) but requires O(n) extra space. Heapsort is in-place and guarantees O(n log n) but is not stable and has poor cache performance.

Non-comparison sorts include counting sort, radix sort, and bucket sort. Radix sort extends counting sort to larger ranges by sorting digit by digit, achieving linear time for fixed-width integers. Bucket sort distributes elements into buckets and sorts each bucket with another algorithm, excelling for uniformly distributed floating-point numbers. Counting sort is the simplest and fastest of the three when k is small, but radix sort is more general for large integers, and bucket sort is better for non-integer data.

In practice, the decision rule is straightforward. If your data consists of integers with k = O(n) or smaller, use counting sort for optimal performance. If k is larger but the number of digits d is small, use radix sort with counting sort as the digit sorter. If your data is floating-point and uniformly distributed, consider bucket sort. Otherwise, for general-purpose sorting of arbitrary comparable data, use the language's built-in sort (usually Timsort or introsort), which is highly optimized and adaptive.

Benchmarks consistently show counting sort outperforming quicksort by 2x to 5x when k is less than n, and by even larger margins when k is much smaller than n. However, when k exceeds n by a large factor, quicksort quickly becomes faster due to counting sort's memory allocation overhead. Always measure with representative data and consider the range check heuristic discussed earlier to make an informed choice.

9. Common Mistakes and Best Practices

Implementing counting sort correctly requires attention to several subtle pitfalls that can lead to incorrect results, excessive memory usage, or loss of stability. Awareness of these common mistakes and adherence to best practices will help you deploy counting sort safely and efficiently in production code.

The most frequent mistake is forgetting to handle negative numbers. A naive implementation that allocates count = [0] * (max_val + 1) and indexes with count[num] will fail with an IndexError or incorrect behavior for negative inputs. Always compute both min and max and use an offset of -min_val, or explicitly validate that inputs are non-negative and raise a clear error otherwise. Similarly, failing to handle empty or single-element inputs can cause max() to throw a ValueError on an empty sequence.

Another critical error is losing stability by traversing the input in the wrong direction during distribution. If you iterate from left to right and place elements using the prefix sum, equal elements will be placed in reverse order, breaking stability. This bug is silent — the output will still be sorted, but any secondary ordering will be lost, which can cause subtle failures in radix sort or when sorting records. Always traverse reversed(arr) or iterate indices from n-1 down to 0 when stability matters.

Pitfalls to Avoid

Memory blowup is the most dangerous pitfall. Allocating a count array of size max - min + 1 without checking the range can exhaust memory or cause the system to swap. For example, sorting [1, 1000000000] would attempt to allocate a billion-element array for just two numbers. Best practice is to check if k is unreasonably large relative to n and fall back to a comparison sort. A common heuristic is to use counting sort only if k <= 5*n or k <= 10**6, depending on memory constraints.

Off-by-one errors are also common, especially in the prefix sum and placement logic. Remember that after prefix sums, count[i] holds the number of elements less than or equal to i, which is the exclusive upper bound for the next value. You must decrement count[idx] before using it as an index (count[idx] -= 1; output[count[idx]] = x), not after. Testing with arrays containing duplicates and with the minimum and maximum values in the range helps catch these errors.

Best Practices

Always document the preconditions and complexity in your function's docstring, including the O(n + k) time and space bounds and the requirement for integer keys. Validate inputs early and provide informative error messages when preconditions are violated. When performance matters, use local variable aliases (e.g., local_count = count) inside loops to reduce attribute lookup overhead in Python, and consider using array('I') or numpy for large count arrays to reduce memory.

Prefer the stable prefix-sum version when writing library code, even if you do not currently need stability, because it preserves more information and is required for composability with radix sort. If you need an in-place version for memory savings, make it explicit in the name (e.g., counting_sort_inplace_unstable) and document that it is not stable. Finally, always benchmark against Python's built-in sorted() for your specific data distribution — for many real-world datasets, Timsort's adaptivity and highly optimized C implementation may still win despite the theoretical advantage of counting sort.

10. Interview Questions

Counting sort is a frequent topic in technical interviews because it tests understanding of non-comparison sorts, complexity analysis, and the ability to recognize when specialized algorithms outperform general ones. Interviewers often use it to assess whether a candidate can reason about tradeoffs and apply the right tool for the job, rather than defaulting to a one-size-fits-all solution.

Question 1: When would you prefer counting sort over quicksort?

Answer: I would prefer counting sort when the input consists of integers in a small, bounded range where k = O(n) or smaller. In that case counting sort runs in O(n) time, which is asymptotically faster than quicksort's O(n log n) average and O(n²) worst case. It is also preferable when stable sorting is required and when predictable worst-case performance is needed, since counting sort's time is deterministic. However, if k is much larger than n, or if the data is not integer-based, quicksort or the language's built-in sort is more appropriate due to counting sort's O(k) memory overhead.

Question 2: How do you make counting sort stable, and why does it matter?

Answer: Counting sort is made stable by computing prefix sums to determine final positions and then traversing the input array in reverse order during distribution. After building the cumulative count array, we iterate from the last element to the first, decrement the count for that key, and place the element at that index in the output. This ensures that among equal keys, the element that appeared later in the input is placed later in the output, preserving relative order. Stability matters because it allows counting sort to be used as a subroutine in radix sort, where stability across digit passes is necessary for correctness, and when sorting records with satellite data where secondary ordering must be preserved.

Question 3: What is the time and space complexity, and what happens if k is very large?

Answer: Counting sort has O(n + k) time complexity for best, average, and worst cases, and O(n + k) auxiliary space for the stable version (O(k) for the unstable in-place reconstruction). Here n is the number of elements and k is the range (max - min + 1). If k is very large, say k is much greater than n, the O(k) term dominates, making the algorithm slower and more memory-intensive than O(n log n) comparison sorts. For example, sorting 10 numbers in range 0 to 10^9 would require a billion-element count array. In practice we check if k is too large relative to n and fall back to a comparison sort to avoid memory blowup.

Question 4: Can counting sort be used to sort strings or floating-point numbers?

Answer: Directly, counting sort only works for integers or data that can be mapped to a small integer range. For strings, we can use counting sort as part of radix sort to sort by individual characters, since characters have a small range (e.g., 256 for extended ASCII or 65536 for Unicode). We sort strings character by character from least to most significant position using stable counting sort per position. For floating-point numbers, counting sort is generally not suitable because the range is huge and values are not discrete. Bucket sort is a better distribution sort for floats, especially if they are uniformly distributed. Alternatively, floats can be reinterpreted as integers via their IEEE 754 bit representation and then radix sorted.

Question 5: Walk through counting sort on [2, 5, 3, 0, 2, 3, 0, 3]

Answer: Input range is 0 to 5, so count array size is 6. Phase 1 counts: C=[2,0,2,3,0,1] (two 0s, two 2s, three 3s, one 5). Phase 2 prefix sum: C=[2,2,4,7,7,8]. Phase 3 distributes in reverse: process 3 → C[3]=7→6 place at 6, next 0 → C[0]=2→1 place at 1, next 3 → C[3]=6→5 place at 5, next 2 → C[2]=4→3 place at 3, next 0 → C[0]=1→0 place at 0, next 3 → C[3]=5→4 place at 4, next 5 → C[5]=8→7 place at 7, next 2 → C[2]=3→2 place at 2. Output is [0,0,2,2,3,3,3,5] sorted. This demonstrates counting, prefix sums, and stable placement.