Counting Sort: An Efficient Algorithm for Specific Scenarios

Counting Sort is a non-comparison-based sorting algorithm. It is highly efficient for sorting elements within a specific range, making it a valuable tool in competitive programming and computer science curricula like GATE. Unlike comparison sorts (like Merge Sort or Quick Sort) that rely on comparing elements, Counting Sort leverages the value of the elements themselves to determine their sorted positions.

How Counting Sort Works

The core idea behind Counting Sort is to count the occurrences of each distinct element in the input array and then use these counts to determine the positions of the elements in the sorted output array. It's particularly effective when the range of input values (k) is not significantly larger than the number of elements (n).

Counting Sort uses auxiliary space to count element frequencies and then place them in their correct sorted positions.

It involves creating a 'count' array to store the frequency of each element and then using this count array to build the sorted output. This avoids direct element comparisons.

The algorithm typically proceeds in three main steps:

Create a Count Array: An auxiliary array, often called count, is created with a size equal to the range of input values (maximum value + 1). This array is initialized to zeros. Iterate through the input array and for each element x, increment count[x].
Modify the Count Array: Transform the count array such that count[i] now contains the actual position of the element i in the output array. This is achieved by cumulatively summing the counts: count[i] = count[i] + count[i-1] for all i from 1 to the maximum value.
Build the Output Array: Create an output array of the same size as the input array. Iterate through the input array in reverse order. For each element x, place it at output[count[x] - 1] and then decrement count[x]. Iterating in reverse ensures stability (elements with the same value maintain their relative order).

What is the primary advantage of Counting Sort over comparison-based sorts?

Its time complexity is linear (O(n+k)) when the range of input values (k) is not significantly larger than the number of elements (n), whereas comparison sorts are typically O(n log n).

Example Walkthrough

Let's sort the array

code

[4, 2, 2, 8, 3, 3, 1]

where the maximum value is 8. The range (k) is 8.

Consider the input array: [4, 2, 2, 8, 3, 3, 1]. The maximum element is 8.

Step 1: Count Array Creation Initialize count array of size 9 (0 to 8) with zeros: [0, 0, 0, 0, 0, 0, 0, 0, 0]. Iterate through input array:

1: count[1] becomes 1.
2: count[2] becomes 1.
2: count[2] becomes 2.
3: count[3] becomes 1.
3: count[3] becomes 2.
4: count[4] becomes 1.
8: count[8] becomes 1. Resulting count array: [0, 1, 2, 2, 1, 0, 0, 0, 1] (Indices represent values 0-8).

Step 2: Modify Count Array (Cumulative Sum) count[0] = 0 count[1] = count[1] + count[0] = 1 + 0 = 1 count[2] = count[2] + count[1] = 2 + 1 = 3 count[3] = count[3] + count[2] = 2 + 3 = 5 count[4] = count[4] + count[3] = 1 + 5 = 6 count[5] = count[5] + count[4] = 0 + 6 = 6 count[6] = count[6] + count[5] = 0 + 6 = 6 count[7] = count[7] + count[6] = 0 + 6 = 6 count[8] = count[8] + count[7] = 1 + 6 = 7 Modified count array: [0, 1, 3, 5, 6, 6, 6, 6, 7].

Step 3: Build Output Array Initialize output array of size 7: [_, _, _, _, _, _, _]. Iterate input [4, 2, 2, 8, 3, 3, 1] in reverse:

Element 1: count[1] is 1. Place 1 at output[1-1] = output[0]. output = [1, _, _, _, _, _, _]. Decrement count[1] to 0.
Element 3: count[3] is 5. Place 3 at output[5-1] = output[4]. output = [1, _, _, _, 3, _, _]. Decrement count[3] to 4.
Element 3: count[3] is 4. Place 3 at output[4-1] = output[3]. output = [1, _, _, 3, 3, _, _]. Decrement count[3] to 3.
Element 8: count[8] is 7. Place 8 at output[7-1] = output[6]. output = [1, _, _, 3, 3, _, 8]. Decrement count[8] to 6.
Element 2: count[2] is 3. Place 2 at output[3-1] = output[2]. output = [1, _, 2, 3, 3, _, 8]. Decrement count[2] to 2.
Element 2: count[2] is 2. Place 2 at output[2-1] = output[1]. output = [1, 2, 2, 3, 3, _, 8]. Decrement count[2] to 1.
Element 4: count[4] is 6. Place 4 at output[6-1] = output[5]. output = [1, 2, 2, 3, 3, 4, 8]. Decrement count[4] to 5.

Final sorted array: [1, 2, 2, 3, 3, 4, 8].

📚

Text-based content

Library pages focus on text content

Time and Space Complexity

Aspect	Counting Sort	Comparison Sorts (e.g., Merge Sort)
Time Complexity (Best/Average/Worst)	O(n + k)	O(n log n)
Space Complexity	O(n + k)	O(n) or O(log n) depending on implementation

Counting Sort is a linear time sorting algorithm, but it's only practical when the range of input values (k) is not excessively large compared to the number of elements (n). If k is much larger than n, its space and time complexity can become prohibitive.

When to Use Counting Sort

Counting Sort is ideal for scenarios where:

The input consists of integers.
The range of input values (k) is known and relatively small.
Stability is required (maintaining the relative order of equal elements).

Common applications include sorting student scores, character frequencies, or data within a limited numerical range. It's also a foundational algorithm for Radix Sort.

What is the main limitation of Counting Sort?

It is not suitable for sorting elements with a very large range of values or non-integer data types.

Learning Resources

Counting Sort - GeeksforGeeks(documentation)

A comprehensive explanation of the Counting Sort algorithm with detailed steps, pseudocode, and complexity analysis.

Counting Sort Algorithm - Tutorialspoint(documentation)

Provides a clear overview of Counting Sort, its working principle, and its time and space complexity.

Counting Sort Explained - YouTube (MyCodeSchool)(video)

A visual and step-by-step explanation of how Counting Sort works, making the concept easier to grasp.

Counting Sort - Programiz(documentation)

Offers a concise explanation and implementation of Counting Sort in various programming languages.

Algorithms - Sorting - Counting Sort - MIT OpenCourseware(video)

Part of a university-level algorithms course, this lecture covers Counting Sort and its relation to Radix Sort.

Introduction to Algorithms (CLRS) - Chapter 8: Sorting in Linear Time(paper)

An excerpt from a renowned algorithms textbook, detailing the theoretical underpinnings and correctness of Counting Sort.

Counting Sort - Wikipedia(wikipedia)

A broad overview of the Counting Sort algorithm, its history, variations, and applications.

Data Structures and Algorithms: Counting Sort - Coursera(video)

A lecture from a popular online course that explains Counting Sort and its efficiency.

Counting Sort Implementation in Python - Real Python(blog)

A practical guide to implementing Counting Sort in Python, with code examples and explanations.

GATE CS Syllabus - Algorithms and Data Structures(documentation)

The official syllabus for GATE Computer Science, which includes Sorting Algorithms as a key topic.