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

  • Wenjie Cao

    Thanks,it did help me~

    • tutorialhorizon

      Thanks Wenjie, good to hear that it was helpful

  • anchal dhiman

    well explain

  • Umut Dönmez

    ty for this code Have a nice day

    • tutorialhorizon

      You r welcome.

  • May

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

%d bloggers like this: