5 ms·
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
by Ecco 7y ago
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.
- war1025 7y agoI 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.
- kadoban 7y agoProbably 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).
- magicalhippo 7y agoBut 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.