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

Question

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.

Answer 1

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.

Answer 2

If n is large, then log(n) is definitively greater than 1, and n*log(n) greater than n. If m is very small compared to n, then O(n+m) is near O(n). So with these given conditions, your algorithm would be faster.

But this better time performance, comes at the cost of the space performance.

Answer 3

Your method is still N*log(n).

The function index(v) is probably a binary search which is log(x). You perform that n times, so your algorithm is n*log(n).