Lesson plan

Insertion sort

Insertion sort is a simple sorting algorithm that builds the final sorted array (or list) one item at a time by comparisons. It is much less efficient on large lists than more advanced algorithms such as quicksort, heapsort, or merge sort. However, insertion sort provides several advantages: * Simple implementation: Jon Bentley shows a version that is three lines in C-like pseudo-code, and five lines when optimized. * Efficient for (quite) small data sets, much like other quadratic (i.e., O(n 2 )) sorting algorithms * May be more efficient in practice than most other simple quadratic algorithms such as selection sort or bubble sort but relative incoming data order and read/write costs matter with high exchange costs and randomly ordered data, selection sort is faster * Adaptive, i.e., efficient for data sets that are already substantially sorted: the time complexity is O(kn) when each element in the input is no more than places away from its sorted position * Stable; i.e., does not change the relative order of elements with equal keys * In-place; i.e., only requires a constant amount O(1) of additional memory space * Online; i.e., can sort a list as it receives it When people manually sort cards in a bridge hand, most use a method that is similar to insertion sort.

Back to article

Article summary

Insertion sort is a simple sorting algorithm that builds the final sorted array (or list) one item at a time by comparisons. It is much less efficient on large lists than more advanced algorithms such as quicksort, heapsort, or merge sort. However, insertion sort provides several advantages: * Simple implementation: Jon Bentley shows a version that is three lines in C-like pseudo-code, and five lines when optimized. * Efficient for (quite) small data sets, much like other quadratic (i.e., O(n 2 )) sorting algorithms * May be more efficient in practice than most other simple quadratic algorithms such as selection sort or bubble sort but relative incoming data order and read/write costs matter with high exchange costs and randomly ordered data, selection sort is faster * Adaptive, i.e., efficient for data sets that are already substantially sorted: the time complexity is O(kn) when each element in the input is no more than places away from its sorted position * Stable; i.e., does not change the relative order of elements with equal keys * In-place; i.e., only requires a constant amount O(1) of additional memory space * Online; i.e., can sort a list as it receives it When people manually sort cards in a bridge hand, most use a method that is similar to insertion sort.

Key claims

No claims recorded.

Discussion questions

  1. Summarise the article in your own words. Which single claim would you verify first, and why?
  2. Which claim in this article is most likely to be revised as the sources update? How would you check its current status?
  3. If two sources disagreed about one of these facts, what would you need in order to trust one over the other?

Bibliography

No sources recorded.

Key claims and bibliography are generated from the same tracked claims and sources as the article page.