Sorting an array of positive integers including 0 much faster than Radix Sort 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) =&gt; t[r] ? (t[r]++,t) : (t[r]=1,t),[]);
    return Object.keys(tmp)
                 .reduce((a,k) =&gt; {
                           for (var i = 0; i &lt; 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.
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.