Why is insertion sort faster than quick sort on a sorted array
java, sorting
Solution
The reason that insertion sort is faster on sorted or nearly-sorted arrays is that when it's inserting elements into the sorted portion of the array, it barely has to move any elements at all. For example, if the sorted portion of the array is `1 2` and the next element is `3`, it only has to do one comparison -- `2 < 3` -- to determine that it doesn't need to move `3` at all. As a result, insertion sort on an already-sorted array is linear-time, since it only needs to do one comparison per element.
Problem
I'm comparing insertion sort with a quicksort. I've figured out why the qsort is slower on an almost sorted array but I cant figure out why the insersion sort is so much quicker, surely it still has to compare nearly as many elements in the array?