# Counting sort

Algorithms Counting sort

As we learned from the article A lower approximation of the sorting problem complexity we cannot sort with a better time complexity than O(n log n). This limitation applies to the decision tree, which must be covered by mutual comparison of the items. However, what if we could sort the items without comparing them? Would we be able to sort the array in linear time? It sounds crazy, but it's totally possible. There are multiple sorting algorithms based on this principle and Counting sort is one of them.

This algorithm only sorts integers, which isn't necessarily a problem because it's what we usually sort. For other values, we can simply convert the data into integers (e.g. multiply the numbers with 2 decimal places by one hundred, sort them, and then divide them again). The sorting part is done using an auxiliary array which is called the counting array, sometimes also the indexing array. The counting array should be as long as

...End of the preview...

ict.social is a large database made up of manuals and tutorials, whose main goal is to provide high-quality IT education to everyone. We started out in the Czech republic, where we display roughly a million articles per month and receive plenty of gratitude from our users. Thanks to our successful establishment, we are now bringing these articles to the rest of the world.

Although we are trying to keep our content free of charge, maintaining the site is a huge effort for everyone involved. Therefore, some content (exercises and more advanced material) costs network points. Don't worry, they're really cheap :)

### Article description

Requested article covers this content:

### Limited offer: Learn all knowledge and save money

 Buy articles and tests separately one by one 20 points Buy the course including all articles and features for an exclusive price 17 points Currently, you have 0 points By buying this exclusive package, you'll have access to all 12 articles in this course including exercise submitting while saving \$0.27. This offer is limited for the first articles only with an additional exclusive 15% discount. You gain 17 points for adding an article to the site, or for \$1.80 \$1.53

Warning, by buying just this article you'll lose the limited 15% discount for the package of all the articles.

 To access the article, you need 10 points Currently, you have 0 points You gain 10 points for adding an article to the site, or for \$0.90

Buying this article gives you unlimited access to it forever. You will learn some more and help us keep giving our site maintenance which helps you and others get better futures. It's a win-win.

You gain points by supporting our network. This is done by sending a helpful amount of money to support the site, or by creating content for the network.

You can get points immediately using:

 Credit card SMS Wire transfer

Article has been written for you by David Jancik
.
Previous article
Quicksort
All articles in this section
Algorithms