# Python implementation · Counting Sort of the top ten sorting algorithms

Posted May 26, 20202 min read

## Introduction

Counting sorting(Counting Sort) is not a sorting algorithm based on comparison. Its core lies in converting the input data value into a key and storing it in an extra array space. As a sort of linear time complexity, count sorting requires that the input data must be an integer with a certain range. Its basic idea is:for each element x in a given input sequence, determine the number of elements in the sequence that are less than or equal to x, and then store x directly in the correct position of the final sort sequence.

## Algorithm implementation steps

1. Apply for additional space based on the difference between the largest and smallest elements in the set to be sorted;
2. Traverse the set to be sorted, and record the number of occurrences of each element in the extra space corresponding to the element value;
3. Calculate the data in the extra space to get the correct position of each element;
4. Move each element of the set to be sorted to the correct position calculated.

## Python code implementation

``````# counting_sort code implementation

from typing import List

def counting_sort(arr:List [int]):
max = min = 0
for i in arr:
if i <min:
min = i
if i> max:
max = i
count = *(max-min +1)
for j in range(max-min + 1):
count [j]= 0
for index in arr:
count [index-min]+ = 1
index = 0
for a in range(max-min + 1):
for c in range(count [a]):
arr [index]= a + min
index + = 1

# Test Data

if __name__ == '__main__':
import random
random.seed(54)
arr = [random.randint(0,100) for _ in range(10)]
print("raw data:", arr)
counting_sort(arr)
print("Count sort results", arr)

# Output result

Original data:[17, 56, 71, 38, 61, 62, 48, 28, 57, 42]
Counting and sorting results [17, 28, 38, 42, 48, 56, 57, 61, 62, 71]``````

## Animated demo ## Analysis of Algorithms

• time complexity

The data range is constant k, the number of elements to be sorted is n, and the total time complexity is \$O(n + k) \$.

• Space complexity

Counting and sorting only requires an extra space complexity of \$O(k) \$, so the sorting and counting space complexity is \$O(k) \$.

• Stability

Counting sorting does not change the relative position of equal elements, so counting sorting is stable.

• Overview

Time complexity(average) Time complexity(best) Time complexity(worst) Space complexity Sort by Stability
\$O(n + k) \$ \$O(n + k) \$ \$O(n + k) \$ \$O(k) \$ out-place stable 