custom array sorting algorithm

Question

So I came up with a "new" sorting algorithm:

function indexSort(array, min, max) {
    var newArray = Array.from({length:Math.abs(max-min)}, () => 0);
    for (let i = 0; i < max; i++) {
        if (array.includes(array[i])) {
            newArray[array[i]] = array[i];
        }
    }
    for (let i = 0; i < newArray.length; i++) {
        if (newArray[i] == 0) { 
            newArray.splice(i, 1); 
            i--;
        }
    }
    return newArray;
}

This algorithm sorts numbers in ascending orders so:

Input -> Output
indexSort([ 3, 1, 2 ], 1, 3) -> [ 1, 2, 3 ]
indexSort([ 64, 12, 9 ], 9, 64) -> [ 9, 12, 64 ]

This algorithm sorts arrays, pretty slow at that, and, has, in its current state some major downsides in comparison to other sorting algorithms:

• Only works with positive integers.
• Has to loop over the entire array twice.
• Doesn't allow for duplicate items.

It has probably other downsides that I cannot currently think of.

So what I want to figure out is:

• Why is this sorting algorithm so slow?
• Is it possible to do everything in just one loop using an else statement?
• Why is this sort outperformed by Bubble Sort?
• What is the big O notation of this algorithm?
• Has this already been discovered and if so, what is the name of it?

Answer 1

I'll try to summarize what's been said in the comments into an answer and add my two cents to it.

First of all I suppose this was made because you had an idea on how to sort numbers and just tried implementing it to see how it'd work out. Nothing wrong with that, but as has been said said, sorting algorithms are very well researched and you'll always be better off using the build-in method or implementing someone else's algorithm if it satisfies some type of requirement (e.g. cycle sort. Not fast, but uses minimum writes). That doesn't mean you shouldn't mess around with sorting any more, as this could be a good way to learn about how they work and why.

As for the algorithm, it seems like your idea was the following:

1. Create an array that fits every number
2. Put the number where they belong, using their value as the index
3. Remove all filler 0s

Now, the purpose of the min / max parameters is clear, they're used to limit the size of the step 1 array. As @ggorlen said, this information is usually not given to sorting algorithms. If this was needed you'd probably iterate over the input array and find them this way. This also prevents someone giving bogus values to the algorithm that result in an invalid output (ex: giving [1,2,3,4], 2, 2 as args yields [<1 empty value>, 1, 2]).

As for the complexity, it's at least O(n²). The oversimplified reason is that you're iterating over an entire array in O(n) and for every iteration you search or splice, which again is O(n), resulting in O(n²). However, since the loops don't iterate over n but over an array with the size max, your complexity can be WAY higher, as seen in @ggorlens comment about the [12341231, 143] case. This comment also answers the question of why this is outperformed by bubble sort; you're doing not one but two passes of bubble-sort complexity over an array that can be way larger than the one bubble sort has to manage.

To my knowledge, this hasn't been discovered, probably because it's neither as fast as the existing algorithms or as interesting as Bogosort, Stooge sort or Stalin sort.

As a final remark, Counting sort may be interesting to you.