Only this week 80 % discount on e-learning courses of C# .NET
Get up to 60 % extra points for free! More info
discount 50

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...
Continue further

You will gain knowledge worth hundreds of thousands for a few crowns

You've come here and that's great! We believe that the first lessons showed you something new and useful
Do you want to continue the course? Go to the premium section.

Limited offer: Learn all knowledge and save money

Buy lessons and exercise submitting one by one $1.80
20.00 points
Buy all currently available lessons with exercise submitting and other features for an exclusive price $1.53 17.00 points
Currently, you have $0
0.00 points
By buying this exclusive package, you'll have access to all 12 lessons in this course including exercise submitting while saving $0.27. This offer is limited for the first lessons only with an additional exclusive 15% discount.

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

Buy only the lesson $0.90
10.00 points
Currently, you have $0
0.00 points

This article is licensed: Premium, by buying this article, you agree with the terms of use.

What will you get from us in the next lessons?
  • Unlimited and permanent access to individual lessons.
  • High quality IT knowledge.
  • Skills to help you get your dream and well-paid job.

Article description

Requested article covers this content:

This article is about Counting sort, which is able to sort numbers according to their value in linear time. Source codes for languages Java,C#,Delphi,Ruby.

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.

Article has been written for you by David Jancik