Algorithm Steps:

  • Start with the second element (assuming the first is already sorted).
  1. Compare the current element with its predecessor.
  2. If the current element is smaller, swap it with its predecessor and repeat until the correct position is found.
  3. Move to the next element and repeat the process until the entire list is sorted.

Real-life Analogy:

Imagine you have a deck of playing cards in your hand, and you want to arrange them in ascending order. You start with the first card, and for each subsequent card, you insert it into its correct position in the sorted part of the deck by comparing and shifting if necessary.

Numerical Form:

Let's consider an example list: [5, 2, 9, 1, 5, 6].

  1. Start: [5] (5 is considered sorted as there's only one element).
  2. Insert 2: [2, 5].
  3. Insert 9: [2, 5, 9].
  4. Insert 1: [1, 2, 5, 9].
  5. Insert 5: [1, 2, 5, 5, 9].
  6. Insert 6: [1, 2, 5, 5, 6, 9].

This list is now sorted.

Examples:

  • Sorting a list of names alphabetically.
  • Arranging a list of dates in chronological order.
  • Sorting a list of integers or floating-point numbers.

Time Complexity:

  • Best Case: O(n) - when the list is already sorted.
  • Average Case: O(n^2) - average performance over all permutations.
  • Worst Case: O(n^2) - when the list is in reverse order.

Insertion Sort is not the most efficient algorithm for large datasets, but it performs well on small lists or nearly sorted data.

Further Reading