Related: One of my favorite realizations back in college was that insertion sort in real life is an optimal sort. The inefficiency in computers is that you need to slide all of the values down a place one by one as you insert numbers. In real life, the values just get shoved down in parallel.
Helped me understand why people default to such an inefficient algorithm when learning about sorting.
> The inefficiency in computers is that you need to slide all of the values down a place one by one as you insert numbers.
You don't need to do this if you use a doubly-linked list, yet the algorithm is still quadratic, so this cannot possibly be the reason why it is quadratic. It is quadratic because you are (in the worst case) comparing every element in the list with every other element in the list.
Sorry mate but that’s just plain wrong... What takes quadratic time in insertion sort is not the insertions but all the comparisons. Otherwise we’d have linear time sort using linked lists.
Probably depends what you're doing with it, physically, but if you were running insertion sort manually it'd be very intuitive to do something like binary search to find the correct insertion point. That would make it O(n lg n).
But if the list of numbers is small enough, our brains essentially finds the insertion position in a single operation.
One could imagine making a CPU which has a similar single-cycle instruction, ie in a list of n<8 numbers find the insertion point of x. Similar to single-cycle adders and multipliers.
Yeah that's kind of cheating, but it would be close to how we do it.
I don't remember the specifics of it, and maybe there were added restrictions, but I do remember working it out to be O(nlog n). Not something I've thought about in a long time.
Helped me understand why people default to such an inefficient algorithm when learning about sorting.