# Counting-Based Sorting

We'll cover the following

In this lesson, we study two sorting algorithms that are not comparison based. Specialized for sorting small integers, these algorithms elude the lower bounds of Theorem 1 in the previous lesson by using (parts of) the elements in as indexes into an array. Consider a statement of the form

$c[a[i]] = 1$

This statement executes in constant time, but has c.length possible different outcomes, depending on the value of a[i]. This means that the execution of an algorithm that makes such a statement cannot be modeled as a binary tree. Ultimately, this is the reason that the algorithms in this section are able to sort faster than comparison-based algorithms.

## Counting-sort

Suppose we have an input array a consisting of $n$ integers, each in the range $0,...,k − 1$. The counting-sort algorithm sorts $a$ using an auxiliary array c of counters. It outputs a sorted version of a as an auxiliary array b.

The idea behind counting-sort is simple: for each $i \in \{0,...,k − 1\}$, count the number of occurrences of i in a and store this in c[i]. Now, after sorting, the output will look like c[0] occurrences of 0, followed by c[1] occurrences of 1, followed by c[2] occurrences of $2,. . . ,$ followed by c[k − 1] occurrences of k − 1.

### Visual demonstration of counting-sort

The code that does this is very slick, and its execution is illustrated below: