Like bubble sort, insertion sort performs very well when the input is pre-sorted. However, it performs considerably better than bubble sort when the input is either randomly or reverse sorted. Although considerably better than bubble sort, it’s performance is still abysmal compared to quick and merge sort for large inputs.
sort: // side effect: rearranges the values in A A = input array for i = 0 to num of items in A: open_index = i temp = A[i] for j = i - 1 to 0: if temp > A[j]: shift A[j] to the right one position open_index += 1 else: end inner loop A[open_index] = temp
Click here for build and run instructions