What type of sorting algorithm is this javascript function?

Question

Here is a function that I wrote to sort small arrays (<1000 elements). When I compared the performance to other examples online (Heap sort and merge sort). I found that mine seemed to perform as well or better. I'm curious what the official name of this type of sort is?

            function Sort(arr) {
                let out = [];
                let Max = 0;
                let Min = 0;
                let cur = 0;

                cur = arr[0];
                Max = cur;
                Min = Max;
                out.push(cur);

                for (let i = 1; i < arr.length; i++) {
                     cur = arr[i];
                    if (Min == Max) {
                        if (cur > Max) {
                            out.unshift(cur);
                            Max = cur;
                        }
                        else {
                            out.push(cur);
                            Min = cur;
                        }
                    }
                    else {
                        if (cur > Max) {
                            out.unshift(cur);
                            Max = cur;
                        }
                        else {
                            if (cur < Min) {
                                out.push(cur);
                                Min = cur;
                            }
                            else {
                                //splice into the middle
                                for (let z = 1; z < out.length; z++) {
                                    if (cur > out[z]) {
                                        out.splice(z, 0, cur);
                                        break;
                                    }
                                }
                            }
                        }
                    }
                }
                return out;
            }

I'm not sure about the name, but it looks like big O is around O(N^3), as soon as simplest obvious sorting algorithm is O(N^2), I doubt that somebody decided to give this one name — Iłya Bursov
– Iłya Bursov, Commented Jan 29, 2016 at 18:55
anyway, I see some similarities to tree sort except that you're using arrays to represent tree — Iłya Bursov
– Iłya Bursov, Commented Jan 29, 2016 at 18:59
@guest271314 here is a link jsfiddle.net/hbzhzact/1. Hit F12 to open the console to view the elapsed times. You will need timestamps enabled. — jsxsl
– jsxsl, Commented Jan 29, 2016 at 20:19

grabantot · Accepted Answer · 2016-01-29 19:00:16Z

3

This part is insertion sort and the rest is special cases handling to make it a bit quicker:

//splice into the middle
for (let z = 1; z < out.length; z++) {
  if (cur > out[z]) {
    out.splice(z, 0, cur);
    break;
  }
}

See animation at https://en.wikipedia.org/wiki/Insertion_sort . The difference is that in your code a new array is created instead of modifying the existing one.

answered Jan 29, 2016 at 19:00

grabantot

2,14920 silver badges35 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

jsxsl Over a year ago

Thanks! It does appear to be similar to insertion sort only not performed inline.

Collectives™ on Stack Overflow

What type of sorting algorithm is this javascript function?

1 Answer 1

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related