Counting Sort

Counting Sort is an sorting algorithm, which sorts the integers( or Objects) given in a specific range.

Algorithm: Time Complexity O(n)

  • Take two arrays, Count[] and Result[] and given array is input[].
  • Count[] will store the counts of each integer in the given array.
  • Update the Count[] so that each index will store the sum till previous step. (Count[i]=Count[i] + Count[i-1]). Now updated Count[] array will reflect the actual position of each integer in Result[].
  • Now navigate the input array taking one element at a time, Count[input[i]] will tell you the index position of input[i] in Result[]. When you do that, decrease the count in Count[input[i]] by 1. See Example




Output :

Orginal Array [2, 1, 4, 5, 7, 1, 1, 8, 9, 10, 11, 14, 15, 3, 2, 4]
Sorted Array : [0, 1, 1, 1, 2, 2, 3, 4, 4, 5, 7, 8, 9, 10, 11, 14, 15]

Top Companies Interview Questions..-

Google Microsoft Amazon Facebook more..

If you find anything incorrect or you feel that there is any better approach to solve the above problem, please write comment.

You may also like...

6 Responses

  1. Wenjie Cao says:

    Thanks,it did help me~

  2. anchal dhiman says:

    well explain

  3. Umut Dönmez says:

    ty for this code Have a nice day

  4. May says:

    original array doesn’t have a ‘0’, where sorted array has that as an extra element

Leave a Reply to Umut Dönmez Cancel reply

Your email address will not be published. Required fields are marked *

This site uses Akismet to reduce spam. Learn how your comment data is processed.

%d bloggers like this: