Counting Sort Algorithm in DSA Go - Cheat Sheet & Quick Revision

Recall & Review

beginner

What is the main idea behind the Counting Sort algorithm?

Counting Sort counts the number of occurrences of each value in the input, then uses these counts to place elements directly into the sorted output.

beginner

What kind of data is Counting Sort best suited for?

Counting Sort works best for sorting integers or objects that can be mapped to integers, especially when the range of input values is not much larger than the number of elements.

intermediate

Why is Counting Sort considered a stable sorting algorithm?

Because it places elements in the output array in the order they appear in the input when counts are equal, preserving the original order of equal elements.

intermediate

What is the time complexity of Counting Sort and why?

The time complexity is O(n + k), where n is the number of elements and k is the range of input values, because it counts occurrences and then builds the output using these counts.

intermediate

What is a major limitation of Counting Sort?

It requires extra space proportional to the range of input values, so it is inefficient if the range is very large compared to the number of elements.

Counting Sort is most efficient when:

A The input contains only strings

B The input is already sorted

C The range of input values is small compared to the number of elements

D The input size is very large and range is huge

Counting Sort works best when the range of input values (k) is small relative to the number of elements (n), making O(n + k) efficient.

What does Counting Sort use to place elements in the output array?

A Comparisons between elements

B Counting the frequency of each element

C Swapping adjacent elements

D Recursive partitioning

Counting Sort counts how many times each value appears and uses these counts to place elements directly.

Is Counting Sort a stable sorting algorithm?

A Yes, it preserves the order of equal elements

B No, it changes the order of equal elements

C Only if the input is sorted

D Only for small inputs

Counting Sort is stable because it places elements in output in the order they appear in input when counts are equal.

What is the space complexity of Counting Sort?

A O(1)

B O(n)

C O(k)

D O(n + k)

Counting Sort uses extra space for the count array of size k and output array of size n, so total space is O(n + k).

Which of these is NOT a step in Counting Sort?

A Swapping elements to sort in place

B Calculating cumulative counts

C Counting occurrences of each value

D Placing elements into output array using counts

Counting Sort does not swap elements in place; it uses counts to build a new sorted output array.

Explain how Counting Sort works step-by-step.

Think about counting first, then using counts to find positions.

What are the advantages and disadvantages of Counting Sort?

Consider speed and memory trade-offs.