2010-10-22, 12:28 AM
What I don't understand about insertion sort, as presented in the original link, is...
Why go back in descending order? Would it not be faster to cut the sorted in half every time by comparing it to the middle element, using log(sorted) instead of linear(sorted) time?
I guess it's a data structure thing? If your sorted data's in a simple array, you need to move all the elements anyway. But if it's in something different where insertion's O(1) then using a log time to find the point seems better.
Why go back in descending order? Would it not be faster to cut the sorted in half every time by comparing it to the middle element, using log(sorted) instead of linear(sorted) time?
I guess it's a data structure thing? If your sorted data's in a simple array, you need to move all the elements anyway. But if it's in something different where insertion's O(1) then using a log time to find the point seems better.