Sorting an array of positive integers including 0 much faster than Radix Sort

Question

I was working on an Limit Order Book structure in JS and came up with this algorithm. I am pretty sure this must have already been implemented but couldn't even find a clue over the web.

The thing is, it's very fast especially when you have an array of many duplicate items. However the real beauty is, after inserting k new items into an array of already sorted n items the pseudo sort (explained below) takes only O(k) and sort takes only O(n+k). To achieve this i keep a pseudo sorted array of m items in a sparse array where m is the number of unique items.

Take for instance we need to sort [42,1,31,17,1453,5,17,0,5] where n is 9 and then we just use values as keys and construct a sparse array (Pseudo Sorted) like;

Value: 1 1 2  2  1  1    1
Index: 0 1 5 17 31 42 1453

Where Value keeps the repeat count. I think now you start to see where I am getting at. JS have a fantastic ability. In JS accessing the sparse array keys can be very fast by jumping over the non existent ones. To achieve this you either use a for in loop of Object.keys().

So you can keep your sparse (pseudo sorted) array to insert new items and they will always be kept in pseudo sorted state having all insertions and deletions done in O(1). Whenever you need a real sorted array just construct it in O(n). Now this is very important in a Limit Order Book implementation because say you have to respond to your clients with the top 100 bids and bottom 100 asks in every 500ms over a web socket connection, now you no longer need to sort the whole order book list again even if it gets updated with many new bids and asks continuously.

So here is sparseSort code which could possibly be trimmed up by employing for loops instead of .reduces etc. Still beats Radix and Array.prototype.sort().

function sparseSort(arr){
    var tmp = arr.reduce((t,r) => t[r] ? (t[r]++,t) : (t[r]=1,t),[]);
    return Object.keys(tmp)
                 .reduce((a,k) => {
                           for (var i = 0; i < tmp[k]; i++) a.push(+k);
                           return a;
                         },[]);
}

Here you can see a bench against Array.prototype.sort() and radixSort. I just would like to know if this is reasonable and what might be the handicaps involved.

Answer 1

I think you re-invented counting sort, but with some small differences. Also you probably need to sort your sparse array keys before iterating over them so that's O(k log k) at least unless your possible range of values is small (let's call it N) so you can just try all N values and it will be O( N ).

Performance wise, it's hard to beat if you have a small range of value N.

Answer 2

So to me this seems to be a really efficient sorting algorithm at least for a very particular case as follows;

1. Sorting positive integers only or negative integers only (zero included).
2. Works much more efficient if you have duplicates
3. Works much more efficient when elements are discontinuous (sparse)

The Array structure in JS is complicated and in time has been optimized greatly. You may like to watch this before proceeding any further but i will try to summarize. Depending on their structures there are basically 6 types of arrays.

PACKED_SMI_ELEMENTS   : [1,2,3]
PACKED_DOUBLE_ELEMENTS: [1.1,2,3]
PACKED_ELEMENTS       : [1,2,"c"]

These are dense arrays and there are three separate optimization layers for them. Then we have three more types coming with their own optimization layers.

HOLEY_SMI_ELEMENTS    : [1,,3]
HOLEY_DOUBLE ELEMENTS : [1.1,,3]
HOLEY_ELEMENTS        : [1,,"c"]

In our case we may have a HOLEY_SMI_ELEMENTS type of array at hand. But i think not all HOLEY_SMI_ELEMENTS type arrays are the same. I guess if the gap between the elements are big enough we end up with a NumberDictionary type where the elements are now of DICTIONARY_ELEMENTS. Now most probably we are here. Normally this is very inefficient compared to normal arrays when normal array operations are performed but in this very particular case it shines. Further reading here.

Now what i couldn't find is, how exactly the number keys (indices) are stored in a NumberDictionary type array. Perhaps balanced BST or Heap with O(log n) access

OK then can we not use a map to start with..? Perhaps we can but it wont be a NumberDictionary and possibly the map keys are not handled like in NumberDictionary. For example In Haskell there is the Map data type which takes two types like Ord k => Map k v which says k type is requried to be a member or Ord type class so that we can apply operations like < or > on k type. Map is implemented on Balanced BST. However there is also an IntMap type where keys have to be Integers. This is how it is explained in Data.IntMap reference.

The implementation is based on big-endian patricia trees. This data structure performs especially well on binary operations like union and intersection. However, my benchmarks show that it is also (much) faster on insertions and deletions when compared to a generic size-balanced map implementation.

It turns out the mentioned big-endian patricia trees are in fact Radix Trees. I think once you end up with a NumberDictionary your keys are stored in a Radix Tree. So in this very algorthm, having duplicates in the array enforce you do Radix sort on keys and count sort on values at the same time. This way of sorting in some particular cases in JS might be reasonable.