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.

• Neil: 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?
• Philip Kendall: What are the complexities of index(v) and value(i)? I suspect you're going to have a log(n) in one of those.
• Neil: @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.
• Frank Puffer: Isn't what you describe a kind of bucket sort or counting sort?
• Pieter B: You'd need a lot of space to store the array with 2 billion values.

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).

• Delioth: 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.