Insertion sort searches the sorted part of the array. It can, on average, stop after looking through half the elements, assuming a uniform distribution for data. Selection sort looks through the unsorted part of the array, which means it must search all the data. In the average case both sorts do O(n2) comparisons, but insertion sort should have a smaller constant than does selection sort.