Insertion Sort Algorithm codepen example is O(n²) for worst AND best case

[roromusic]

Please correct me if I am wrong, but I believe the Insertion Sort algorithm on codepen is O(n²) regardless if the array is mostly sorted or not. This can be observed by the fact that if you pass in a completely sorted array, there are still 45 comparisons made. This can also be observed by the fact that it is as performant as an optimized Bubble Sort. Also, as I understand, Array.splice is an O(n) operation and should be avoided if possible. This is a little nit-picky, but I believe it might come up during coding interviews.

Here is my implementation, which is O(n) when the array is mostly sorted. I am sure there is a cleaner way to write it than my implementation, however.

[shriprem]

I find that Bubble sort is most performant if the input array is already sorted. And, Insert sort is most performant if the input array is sorted in the reverse order. By performant, I mean the minimum number of comparisons needed to complete the sort of an array with a specific length.

I tracked two metrics: number of comparisons, and number of swaps.

Case 1: When the input array is already sorted

 Input: [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
Output: [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

Bubble Sort Metrics: 9 comparisons, 0 swaps Insert Sort Metrics: 45 comparisons, 0 swaps

Case 2: When the input array is reverse sorted

 Input: [9, 8, 7, 6, 5, 4, 3, 2, 1, 0]
Output: [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

Bubble Sort Metrics: 90 comparisons, 45 swaps Insert Sort Metrics: 9 comparisons, 9 swaps

[shriprem]

I looked into why Brian's solutions for the Bubble sort and Insertion sort were returning comparison counts different than mine. I find there are a minor modifications that need to me made in Brian's version of the code: two in the Bubble sort code and one in the Insertion sort code.

[Note that in case of Bubble sort, the impact on comparison count is trivial in relation to O(n²). But for Insertion sort, the change does substantially reduce the comparison count for the best case input for the sort.]

Bubble sort changes:

1. On line 22, the upper limit of the loop counter variable needs to be set at nums.length - 1 instead of just nums.length. This is since we are accessing nums[i + 1] inside the loop. In JavaScript, array index being out of range just returns undefined, and doesn't throw an error; nor will it cause a bug in this particular looping logic. In other languages like Python, the higher index value does result in an error. So the changed line should be: for (var i = 0; i < nums.length - 1; i++) {

2. On line 32, the call to snapshot is actually adding an extra count to the comparisons. So I have commented out in my fork of Brian's code.

My source can be seen here: https://codepen.io/shriprem/pen/JzQOMB?editors=0010#0

Insert sort change: On line 23 of my fork of Brian's code ( https://codepen.io/shriprem/pen/MxMOKb?editors=0010#0 ), I have added a break; statement. This will optimize the sort since once an insertion spot is found for an element among one of its preceding elements, there is no need to continue looking through the rest of the preceding elements.