Is this a sorting algorithm faster than O(n*log(n))

algorithmssorting

If there are n variables each with m possible values. (For integer, m is 2 billion something.)

First, map every possible value to an integer from 0 to m-1 in order.
And define the mapping functions. 

index(v): value to integer
value(i): integer to value

Second, loop the n variables and count how many times every value appeared.

for v in variables {
    counter[index(v)] += 1
}

Finally, loop the counter array and put the values in the result array.

for i in 0...m-1 {
    for j in 1...counter[i] {
        result.append(value(i))
    }
}

The result array would be sorted, and the complexity of this algorithm is O(n+m).

Could be better than O(n*log(n)) for large n and small m.

Best Answer

Congratulations, you have re-invented counting sort! (I'm not being sarcastic, things independently being re-invented multiple times is a good thing, it shows that it is a natural and good way to solve problems.)

The time complexity of counting sort is indeed better than O(n * log n). Note that the usually cited "barrier" of Ω(n * log n) for "sorting" is wrong. This is the lower bound for comparison-based sorting, and not for all sorting.

In particular, counting sort is not based on comparisons, and thus the lower bound for comparison-based sorting does not apply.

Related Topic