# Implementation of Counting Sort Algorithm in Python

By | March 13, 2021

Hi, in this tutorial, we are going to write a simple program implementation for Counting Sort Algorithm in Python.

## Counting Sort Algorithm

Before writing the source code or program for count sort, we first understand what is Count Sort Algorithm in programming.

So, Counting Sort is an Integer-based algorithm that means the numbers or the values of the input received from the user must be or assumed to be integers like in bucket sort and radix sort algorithm.

One thing about Count Sort is that it is among the fastest sorting algorithms around in data structures.

The particular distinction for count sort is that it creates a bucket for each value and keep a counter in each bucket.

Then each time a value is encountered in the input collection, the appropriate counter is incremented.

Because count sort creates a bucket for each value, an imposing restriction is that the maximum value in the input array is known beforehand.

Counting sort is used when there are smaller integers with multiple or large counts in a particular array.

### Implementation of Count Sort

#### 1. Define Counting Sort Function

So first we are going to define a Counting Sort function which basically accepts the input array from the user and then returns sorted array back to the function call.

Now, what we are going to do first is to find the maximum value of an integer in an array and then assign buckets according to the maximum value of the array.

Since the values range from 0 to k, create k+1 buckets.

Now, we have to fill those buckets, so for that iterate through the input array and every time when an item appears, increment the counter in its bucket.

After this iterate through the buckets and we know that each bucket represent value in array

So for each bucket, from smallest value to largest, add the index of the bucket to the input array and decrease the counter in said bucket by one; until the counter is zero.

Worst Case Complexity: O(n+k)
Best Case Complexity: O(n+k)
Average Case Complexity: O(n+k)

where n is the size of the input array and k means the values range from 0 to k.

#### 2. Define Main Function

Since we have implemented counting sort in the first step, now let’s call the counting sort function from step 1 in the main method.

It will simply accept list input by the user and then return the sorted list back to the function call and then we will print the sorted list back to the console.

#### Source Code

``````def countingSort(myList):
maxValue = 0
for i in range(len(myList)):
if myList[i] > maxValue:
maxValue = myList[i]

buckets =  * (maxValue + 1)

for i in myList:
buckets[i] += 1

i = 0
for j in range(maxValue + 1):
for a in range(buckets[j]):
myList[i] = j
i += 1

return myList

if __name__ == '__main__':
sortedList = countingSort([1,23,4,5,6,7,8])
print(sortedList)``````
##### Output Hope you guys like the tutorial, feel free to drop any comments in the comment section down below.
{"ft_lang_label":"__label__en","ft_lang_prob":0.8286733,"math_prob":0.96367174,"size":2954,"snap":"2021-43-2021-49","text_gpt3_token_len":663,"char_repetition_ratio":0.13966101,"word_repetition_ratio":0.019379845,"special_character_ratio":0.22545701,"punctuation_ratio":0.0890411,"nsfw_num_words":0,"has_unicode_error":false,"math_prob_llama3":0.99553794,"pos_list":[0,1,2],"im_url_duplicate_count":[null,2,null],"WARC_HEADER":"{\"WARC-Type\":\"response\",\"WARC-Date\":\"2021-10-17T03:28:24Z\",\"WARC-Record-ID\":\"<urn:uuid:ed8401a5-9175-4a05-90dc-65052e342822>\",\"Content-Length\":\"58444\",\"Content-Type\":\"application/http; msgtype=response\",\"WARC-Warcinfo-ID\":\"<urn:uuid:6737c785-00d6-40ed-a100-847e1e664ec0>\",\"WARC-Concurrent-To\":\"<urn:uuid:9e2b4a45-ee18-4ac7-be98-2901c0ceac6a>\",\"WARC-IP-Address\":\"172.67.72.18\",\"WARC-Target-URI\":\"https://codezup.com/implementation-of-counting-sort-algorithm-in-python/\",\"WARC-Payload-Digest\":\"sha1:ZMXCZT24BOFYK2AR7GCZVPIMNLYG4WGR\",\"WARC-Block-Digest\":\"sha1:7G3FMV5IPQKTIDNBRUZLI6TJ3NAYV3M2\",\"WARC-Identified-Payload-Type\":\"text/html\",\"warc_filename\":\"/cc_download/warc_2021/CC-MAIN-2021-43/CC-MAIN-2021-43_segments_1634323585120.89_warc_CC-MAIN-20211017021554-20211017051554-00589.warc.gz\"}"}