Search⌘ K
AI Features
Home
Courses
Data Structures with Generic Types in Python

Counting-Based Sorting

Explore counting-based sorting methods including counting-sort and radix-sort, and understand how these algorithms efficiently sort integer arrays. Learn their implementations, time complexities, stability properties, and how they surpass traditional comparison-based sorting techniques.

We'll cover the following...

In this lesson we’ll learn about two sorting algorithms that are not comparison-based. Specialized for sorting small integers, these algorithms elude the lower-bounds of Theorem 1 in previous lesson by using (parts of) the elements in a as indices into 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 aa consisting of nn integers, each in the range 0,...,k−10,...,k − 1. The counting-sort algorithm sorts aa using an auxiliary array c of counters. It outputs a sorted version of a as an auxiliary array b.b.

The idea behind counting-sort is simple: For each i∈{0,...,k−1}i \in \{0,...,k − 1\} ...