# Is there an O(n) integer sorting algorithm?

AlgorithmLanguage AgnosticSortingTime Complexity## Algorithm Problem Overview

The last week I stumbled over this paper where the authors mention on the second page:

> Note that this yields a linear running time for integer edge weights.

The same on the third page:

> This yields a linear running time for integer edge weights and O(m log n) for comparison-based sorting.

And on the 8th page:

> In particular, using fast integer sorting would probably accelerate GPA considerably.

Does this mean that there is a O(n) sorting algorithm under special circumstances for integer values? Or is this a specialty of graph theory?

**PS:**

It could be that reference [3] could be helpful because on the first page they say:

> Further improvements have been achieved for [..] graph classes such as integer edge weights [3], [...]

but I didn't have access to any of the scientific journals.

## Algorithm Solutions

## Solution 1 - Algorithm

Yes, Radix Sort and Counting Sort are `O(N)`

. They are NOT comparison-based sorts, which have been proven to have `Ω(N log N)`

lower bound.

To be precise, Radix Sort is `O(kN)`

, where `k`

is the number of digits in the values to be sorted. Counting Sort is `O(N + k)`

, where `k`

is the range of the numbers to be sorted.

There are specific applications where `k`

is small enough that both Radix Sort and Counting Sort exhibit linear-time performance in practice.

## Solution 2 - Algorithm

Comparison sorts must be at least Ω(n log n) on average.

However, counting sort and radix sort scale linearly with input size – because they are not comparison sorts, they exploit the fixed structure of the inputs.

## Solution 3 - Algorithm

Counting sort: http://en.wikipedia.org/wiki/Counting_sort if your integers are fairly small. Radix sort if you have bigger numbers (this is basically a generalization of counting sort, or an optimization for bigger numbers if you will): http://en.wikipedia.org/wiki/Radix_sort

There is also bucket sort: http://en.wikipedia.org/wiki/Bucket_sort

## Solution 4 - Algorithm

While not very practical (mainly due to the large memory overhead), I thought I would mention Abacus (Bead) Sort as another interesting linear time sorting algorithm.

## Solution 5 - Algorithm

These hardware-based sorting algorithms:

A Comparison-Free Sorting Algorithm

Sorting Binary Numbers in Hardware - A Novel Algorithm and its Implementation

Laser Domino Sorting Algorithm - a thought experiment by me based on Counting Sort with an intention to achieve `O(n)`

time complexity over Counting Sort's `O(n + k)`

.

## Solution 6 - Algorithm

Adding a little more detail - Practically the best sorting algorithm till date is not O(n), but O(n √(log log n)) expected time.

You can check more details about this algorithm in *Yijie Han & Mikkel Thorup*'s FOCS '02 paper.