Counting Sort

What is Counting Sort?

• builds the final sorted array one item at a time by comparing each new item to the already sorted items and inserting it into the correct position

• is a non-comparison sorting algorithm that sorts elements by counting the number of occurrences of each unique element

• repeatedly steps through the list, compares adjacent elements, and swaps them if they are in the wrong order.

• is an in-place comparison sorting algorithm that divides the input list into two parts: the sorted part at the front and the unsorted part at the back.

Time Complexity Counting Sort

• O(n)

• O(n)^2

• O(n+k)

• O(1)

Space Complexity Counting Sort

• O(1)

• O(n)

• O(0)

• O(n+k)

counting sort is Stable?

• Yes

• No

Counting sort in place?

• YES

• NO

What are the advantagees of the Counting Sort

• 1) Linear time complexity for a fixed range of input. 2)Efficient for sorting integers.

• 1)Stable and in-place. 2)Works well on nearly sorted data

• 1)Simple to understand and implement. 2)Efficient for small datasets.

• 1)Simple to implement. 2) Performs well on small lists

Counting Sort offers better performance on specific types of data with limited ranges but ...?

• no stability

• uses more time

• uses more memory

• no but