3 ms·

There are two variations of insertion sort. You are comapring to the swapless insertion sort, the other poster is comparing to the swap basses insertion sort. T

There are two variations of insertion sort. You are comapring to the swapless insertion sort, the other poster is comparing to the swap basses insertion sort. This is the swap based insertion sort with a small variation. As discussed, unlike insertion sort it begins by finding the max element and places it first. Following that it follows normal insertion sort pattern with one change. Insertion sort normally sorts the new element "downward". This sort sorts the new element "upward" from the smallest item. It still uses the same inline temporary slot that insertion sort uses, it's just more notable now because it's inserting the new item "bottom-up".

thaumasiotes 2y ago
> Following that it follows normal insertion sort pattern with one change. Insertion sort normally sorts the new element "downward". This sort sorts the new element "upward" from the smallest item. It still uses the same inline temporary slot that insertion sort uses, it's just more notable now because it's inserting the new item "bottom-up". Well, the reason that's more notable is that doing it upward requires you to use swaps instead of an assignment chain. Going downward, you can remember the value you're going to insert all the way down the chain. Going upward, you're always overwriting a value that you must immediately remember, which is worse.