---

📘 Counting Sort

Counting Sort is a non-comparison-based, linear-time sorting algorithm used to sort integers when the range of values (k) is not too large.

It works by counting the number of occurrences of each input element.

---

📌 Key Idea

1. Find the range of input (max value).
2. Create a count array to store frequency of each element.
3. Convert count array into prefix sum array (cumulative counts).
4. Build the output array by placing elements in correct positions.
5. Copy output array to original array.

---

📘 When Counting Sort is Efficient?

Counting Sort is very fast when:

• Data is integer-based
• Range k (max value) is small compared to n
• Suitable for:
  • Exam marks (0–100)
  • Age grouping (0–120)
  • Limited-range IDs
  • Frequency sorting

---

📌 Time and Space Complexity

Complexity	Value
Time	O(n + k)
Space	O(n + k)

Where:

• n = number of elements
• k = range of input values (max − min + 1)

---

📘 Characteristics

• Not based on comparisons
• Stable (in stable implementation)
• Fastest for small range data
• Not in-place (requires extra arrays)
• Works only for non-negative integers (or integers after shifting)

---

📘 Python Implementation of Counting Sort

✔ Stable Version (Recommended for Exams)

def counting_sort(arr):
    if len(arr) == 0:
        return arr
    
    # Step 1: Find the maximum value
    max_val = max(arr)
    
    # Step 2: Create count array
    count = [0] * (max_val + 1)
    
    # Step 3: Count occurrences
    for num in arr:
        count[num] += 1
    
    # Step 4: Cumulative (prefix sum) count
    for i in range(1, len(count)):
        count[i] += count[i - 1]
    
    # Step 5: Build output array (stable sorting)
    output = [0] * len(arr)
    
    # Traverse original array backwards to maintain stability
    for num in reversed(arr):
        count[num] -= 1
        output[count[num]] = num
    
    return output


# Example usage
arr = [4, 2, 2, 8, 3, 3, 1]
sorted_arr = counting_sort(arr)
print("Sorted array:", sorted_arr)

---

📘 Example Output

Sorted array: [1, 2, 2, 3, 3, 4, 8]

---

📘 Non-Negative Integer Requirement

If array contains negatives, convert using:

• Find min_val
• Shift all values by -min_val
• Apply counting sort
• Shift back

(I can provide this code if needed.)

---

📘 Summary (Exam Notes)

• Counting Sort uses frequency counting, not element comparison.
• Time = O(n + k) → linear when k is small.
• Useful for small-range integers.
• Stable sorting if implemented correctly.
• Not in-place due to extra arrays.
• Works best when range (k) is small relative to n.

---