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.
Konrad Zuse created the insertion sort algorithm in 1945 in the first high level language: Plankalkül
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