# Counting-Based Sorting

Learn about counting-based sorting algorithms.

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:

Create a free account to access the full course.

By signing up, you agree to Educative's Terms of Service and Privacy Policy