In this section, 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 a as indexes to an array. Consider a statement of the form

c[a[i]]=1c[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 nn integers, each in the range 0,...,k10,...,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{0,...,k1}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, \dots , 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