×

# Counting sort is called stable and non-comparison sort.

 0 Why counting sort is called stable and non-comparison sort? asked 17 Jan '17, 00:05 2★rashedcs 497●4●12●50 accept rate: 4%

 4 @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). answered 17 Jan '17, 00:52 5★srd091 1.6k●1●11 accept rate: 42%
 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported
• mathemetical formulas in Latex between \$ symbol

Question tags:

×830

question asked: 17 Jan '17, 00:05

question was seen: 761 times

last updated: 17 Jan '17, 00:52