Big O Visualizer

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.

Complexity

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.

Algorithm

Below the implementation of Counting Sort as used on this page.

1export default class CountingSort extends Algorithm {
2  name = "Counting Sort"
3  timeComplexityBest = Complexities.bilinear
4  timeComplexityAverage = Complexities.bilinear
5  timeComplexityWorst = Complexities.bilinear
6
7  execute(array: number[]): void {
8    let min = Number.MAX_VALUE
9    let max = Number.MIN_VALUE
10
11    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    }
16
17    let i = min
18    let j = 0
19    const len = array.length
20    const count = []
21
22    for (i; i <= max; i++) {
23      this.incrementOpCounter()
24      count[i] = 0
25    }
26
27    for (i = 0; i < len; i++) {
28      this.incrementOpCounter()
29      count[array[i]] += 1
30    }
31
32    for (i = min; i <= max; i++) {
33      this.incrementOpCounter()
34      while (count[i] > 0) {
35        this.incrementOpCounter()
36        array[j] = i
37        j++
38        count[i]--
39      }
40    }
41  }
42}