Counting sort is an integer sorting algorithm. That means it is specifically designed to sort lists consisting of (small) numbers. It operates by counting the number of objects that have each distinct key value, and using arithmetic on those counts to determine the positions of each key value in the output sequence.
Counting Sort has a bilinear time complexity for all cases. The amount of operations can be calculated by taking the length of the list n
and the difference between the biggest and the smallest element of the list k
. Adding these two variables gives us a bilinear time complexity of O(n+k)
.
This means that the run time is identical regardless whether the input is randomized, sorted or reversed, as both n
and k
remain the same.
The run time improves when k
is minimal, which is the case for lists of identical numbers.
In contrast, the run time worsens (drastically) when k
is large. For instance, given a tiny array of just ten numbers, but where each number is a value between zero and a million, Counting Sort requires millions of operations to sort the array.
Below the implementation of Counting Sort as used on this page.
1export default class CountingSort extends Algorithm {2 name = "Counting Sort"3 timeComplexityBest = Complexities.bilinear4 timeComplexityAverage = Complexities.bilinear5 timeComplexityWorst = Complexities.bilinear67 execute(array: number[]): void {8 let min = Number.MAX_VALUE9 let max = Number.MIN_VALUE1011 for (let i = 0; i < array.length; i++) {12 this.incrementOpCounter()13 min = Math.min(min, array[i])14 max = Math.max(max, array[i])15 }1617 let i = min18 let j = 019 const len = array.length20 const count = []2122 for (i; i <= max; i++) {23 this.incrementOpCounter()24 count[i] = 025 }2627 for (i = 0; i < len; i++) {28 this.incrementOpCounter()29 count[array[i]] += 130 }3132 for (i = min; i <= max; i++) {33 this.incrementOpCounter()34 while (count[i] > 0) {35 this.incrementOpCounter()36 array[j] = i37 j++38 count[i]--39 }40 }41 }42}