91 Question 2 If an array is already sorted then insertion s

9.1) Question #2

If an array is already sorted, then insertion sort will be faster than selection sort or even mergesort. Why is this?

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. It depends on several factors. Insertion sort will be more efficient that quick sort on small data sets. It also depends on your backing list implementation (LinkedList or ArrayList). Lastly, it also depends on whether there is any kind of ordering to the input data. For example, if your input data is already sorted in the opposite order and you use a LinkedList, the insertion sort will be blazing fast.

Usually, insertion sort will perform less comparisons than selection sort, depending on the degree of \"sortedness\" of the array. While selection sort must scan the remaining parts of the array when placing an element, insertion sort only scans as many elements as necessary. That means that when the array is already sorted or almost sorted, insertion sort performs in O(n) time.

One advantage of selection sort over insertion sort, is that the number of writes (swaps) is in O(n), while in insertion sort it is in O(n^2). This may be important if you are sorting on Flash memory, for example, because writes reduce the lifespan of Flash memory.