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

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.

• Perhaps I'm not understanding what you mean, but wouldn't index(v) simply return 0, 1, 2, 3, 4...? Your first pass would create an array counter full of 1s, would it not?
– Neil
Dec 19, 2018 at 7:13
• What are the complexities of `index(v)` and `value(i)`? I suspect you're going to have a `log(n)` in one of those. Dec 19, 2018 at 7:18
• @PhilipKendall For this, he could simply do an old fashioned loop by index and have both index and value without any extra work, unless I misunderstood what he meant by these functions.
– Neil
Dec 19, 2018 at 7:22
• Isn't what you describe a kind of bucket sort or counting sort? Dec 19, 2018 at 7:46
• You'd need a lot of space to store the array with 2 billion values. Dec 19, 2018 at 10:34

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.

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.

• Why on earth would that be a search - it's a value-index conversion. For an integer, `index(v)` is literally `x => return x`, more generally it's taking a thing and directly finding a sortable value of that thing (usually, probably a property access - `x.getId()` or whatever). That function should be O(1) in most cases. It'd only be a search if you already had a sorted list to know where it should go. Dec 19, 2018 at 19:09