Did I just sort in O(n) on JavaScript?

Question

Using underscorejs library, I tried to abuse the indexing of a JavaScript object, in order to sort an array a of integers or strings:

_(a).chain().indexBy(_.identity).values().value()

I realize it is kind of a "hack", but it actually yielded a sorted array in O(n) time...

Am I dreaming?

Answer 1

Your algorithm is not a comparison sort:

A comparison sort is a type of sorting algorithm that only reads the list elements through a single abstract comparison operation (often a "less than or equal to" operator or a three-way comparison) that determines which of two elements should occur first in the final sorted list.

You are using knowledge about the structure of the values (i.e. knowing that they're integers or strings) in your algorithm, by using those integers/strings as indexes. You are not adhering to the limitations imposed on a comparison sort, and thus you are not restricted to the O(n log n) boundary on time complexity.

Answer 2

You aren't actually sorting anything.

Instead, you're building a hashtable and traversing it in hash order, which may be the same as sorted order for some sets.

Answer 3

It is possible to sort by O(n) using Bucket Sort http://en.wikipedia.org/wiki/Bucket_sort which is I believe what you attempted to write here, but as mentioned above you can't rely on the order of values of an object.

It is possible to sort this way in O(n) if you have limited number of values.

Answer 4

Yes, you are dreaming :-)

It beggars belief that you would have found such a holy grail by accident. If that sequence of operations is a comparison-based sort, people who know this stuff have actually proven that it cannot be done in O(n) time.

I strongly suggest you run that code with dataset sizes of 10, 100, 1000, and so on and you'll see your assumption is incorrect.

Then check to see if you are actually sorting the array or whether this is just an artifact of its organisation. It seems very likely that the indexBy is simply creating an index structure where the order just happens to be the sort order you want, not something that would be guaranteed for all inputs.