# Big O Visualizer

## Counting Sort

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

`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}`