# Is this a new sorting algorithm?

I just came up with a simple sorting algorithm that is faster than ShellSort when the range of values is smaller than the number of elements. Is this new? And if so, what should I do with it?

https://github.com/Frazer/hashSort

let hashSortNonUnique = (unsortedArray)=>{
let myHash = {}
let min = Infinity;
let max = -Infinity;

unsortedArray.forEach(val=>{
myHash[val]=myHash[val]?myHash[val]+1:1;
if(val>max) max = val;
if(val<min) min = val;
});

let count = 0;

for (let sorter = min; sorter <= max; sorter++) {
let num = myHash[sorter];
while(num--){
unsortedArray[count]=sorter;
count++;
}
}
return unsortedArray;
}

let hashSortObjectsWithNonUniqueVals = (unsortedArray,valFunction)=>{
let myHash = {}
let min = Infinity;
let max = -Infinity;

unsortedArray.forEach(val=>{
v= valFunction(val);
myHash[v]=myHash[v]?myHash[v].push(val):[val];
if(v>max) max = v;
if(v<min) min = v;
});

let count = 0;

for (let sorter = min; sorter <= max; sorter++) {
let vals = myHash[sorter];
for (let index = 0; index < vals.length; index++) {
unsortedArray[count]= vals[index];
count++;
}
}
return unsortedArray;
}

• This is not a site for programming questions, so we'd prefer it if you give a high-level description of your algorithm instead of an implementation. This also makes it easier to see if you algorithm is a (variant of) another sorting algorithm. – Discrete lizard May 3 at 5:08

The first is a counting sort with the change that you use a hashtable instead of an array to hold the mapping between element value and the number of elements of that value.

The second is a near textbook Bucket Sort with the change that you don't sort the bucket.

This algorithm is known, however it is not used widely. Essentially this algorithm is
O(max - min + n), which as you state if max-min is approximately n then this algorithm runs in O(2n + e) where e is the small cost of making a hash table, which while read/writes are essentially O(1) they are not always.

But as you can guess the reason this is not used except in special cases is because for most of your data you will have ranges that exceed n lg(n) in which case, quickSort/heapSort/mergeSort/binaryInsertionSort would all out perform it.

Note that even if all but 1 of your elements are in the range [1, n] but you have a single value of n^4 then this algorithm becomes O(n^4). So while highly efficient for closely packed values it is not useful for general purpose where we expect to see large ranges within the list.

For those who dont want to read the code:

function hash_sort( S )

create a hash table H
place the counts of elements of S into H

min := smallest element of S
max := largest element of S

T := array
for each number from min to max
if number is in H
place number into T based on H[number]