Insertion Sort

More notes coming soon!

  • For each item in the unsorted input sequence, insert into the correct position in the sorted output sequence.

  • A naïve solution involves creation of a separate data structure.

  • Memory efficient version swaps items one-by-one towards the left until they land in the right place. The invariant for this type of insertion sort is that every item to the left of position ii is in sorted order, and everything to the right has not yet been examined. Every swap fixes exactly one inversion.

Example

Complexity

  • In the best case, insertion sort takes Θ(N)\Theta(N) time. In the worst case, Θ(N2)\Theta(N^2) time. More generally, runtime is no worse than the number of inversions.

  • Insertion sort is very fast for arrays that are almost sorted, i.e. that have Θ(N)\Theta(N) inversions. It is also fastest for small NN (roughly N<15N < 15).

Visualization

results matching ""

    No results matching ""