Python Program for Counting Sort

What is counting sort ?

Counting Sort Algorithm

Finds maximum element in the list of elements.

Initialize counter list with 0 for all elements range from 0 to maximum element.

Finds frequency for all array elements and updates frequency value in counter list.

Sorted array elements based on counter list.

Counting Sort Steps

Counting Sorting Time complexity

Counting sort time complexity is O(N+K), here N is the number of array elements. K is the maximum element in the array.

Counting Sort Python Program

#!/usr/bin/python                                                               
                                                                                
                                                                                
def counting_sort(list_vals):                                                   
                                                                                
    # finds max val in the list.                                                
    max_val = max(list_vals);                                                   
                                                                                
    list_counts = [];                                                           
    list_sorted = [];                                                           
    # Initialize each elements count as 0                                       
    list_counts = [0 for i in range(0, max_val +1)];                            
                                                                                
    # finds frequency of each array elements                                    
    for i in range(0, len(list_vals)):                                          
        list_counts[list_vals[i]] += 1;                                         
    # adds elements in sorted order based on frequency.                         
    for i in range(0, max_val+1):                                               
        while (list_counts[i]>0):                                               
            list_sorted.append(i);                                              
            list_counts[i] -= 1;                                                
                                                                                
    return list_sorted;                                                         
                                                                                
if __name__ == "__main__":                                                      
    list_vals = [3, 1, 2, 3, 6, 8, 5, 4];                                       
    print("Collection before sorting: %s" % str(list_vals));                    
    print("Sorted list elements: %s" % str(counting_sort(list_vals)));                                                                                                                                           

$ python counting_sort.py 
Collection before sorting: [3, 1, 2, 3, 6, 8, 5, 4]
Sorted list elements: [1, 2, 3, 3, 4, 5, 6, 8]