Why counting sort is called stable and non-comparison sort?
@rashedcs It’s a non-comparison sorting technique as it works by counting the number of elements having distinct key values and then doing some arithmetic to calculate the position of each element in the output sequence and hence it does not compare elements to sort unlike other commonly used sorting technique like merge sort, quick sort, etc.,
Consider an example when you find an item with key x, knowing that it may have other information that distinguishes it from other items with the same key, you don’t just increment a counter for bucket x (which would discard all those extra information). Instead, you have a linked list (or similarly ordered data structure with constant time amortized append) for each bucket, and you append that item to the end of the list for bucket x as you scan the input left to right. So, it just dumps them back into one sorted list.
For a better explanation, you can refer to this answer**(link)**.
2 Likes