Insertion sort animation/visualization

To use this tool effectively, please read instructions here.

Insertion Sort

Insertion Sort is like organizing a hand of playing cards. You take one card at a time and place it in its correct position among the cards you’ve already sorted.

Algorithm description

1. Start with the second element (consider the first element as already sorted)
2. Compare the current element with the elements in the sorted portion
3. Shift all larger elements one position to the right
4. Insert the current element into its correct position
5. Repeat for all remaining elements

Example with Array: [5, 2, 8, 1, 9]

Initial: [5, 2, 8, 1, 9] (consider 5 as sorted)

Step 1 - Process 2:

• Compare 2 with 5 → 2 < 5 → shift 5 right → insert 2 → [2, 5, 8, 1, 9]

Step 2 - Process 8:

• Compare 8 with 5 → 8 > 5 → insert 8 after 5 → [2, 5, 8, 1, 9]

Step 3 - Process 1:

• Compare 1 with 8 → 1 < 8 → shift 8 right
• Compare 1 with 5 → 1 < 5 → shift 5 right
• Compare 1 with 2 → 1 < 2 → shift 2 right
• Insert 1 at beginning → [1, 2, 5, 8, 9]

Step 4 - Process 9:

• Compare 9 with 8 → 9 > 8 → insert 9 after 8 → [1, 2, 5, 8, 9]

Array is now sorted!

The card Analogy

Imagine you’re sorting playing cards in your hand:

• You pick the next card from the deck.

• Compare it with the cards already in your hand.

• Shift the bigger cards one place to the right.

• Insert the card in its correct spot.

• Repeat until all cards are in order.

consider that:

The left side of your array (or hand) is always sorted.

You keep growing this sorted portion one element at a time.

Characteristics of insertion sort

• Time Complexity:

  • Worst case: O(n²) - when array is reverse sorted
  • Best case: O(n) - when array is already sorted
  • Average case: O(n²)

• Space Complexity: O(1) - sorts in-place

• Stable: Yes, equal elements maintain relative order
• Adaptive: Performs well on partially sorted arrays
• Online: Can sort lists as they're received

Simple Implementation

def insertion_sort(arr):
    for i in range(1, len(arr)):
        key = arr[i]  # Current element to be positioned
        j = i - 1

        # Shift elements greater than key to the right
        while j >= 0 and arr[j] > key:
            arr[j + 1] = arr[j]
            j -= 1

        # Insert key at correct position
        arr[j + 1] = key

    return arr

Advantages

• Efficient for small datasets
• Simple to implement
• Low overhead
• Stable sorting
• Works well with nearly-sorted data
• Online algorithm - can sort as data arrives

Real-World Use Cases

Insertion Sort is commonly used:

• In practice for small arrays (often as part of hybrid algorithms like Timsort)
• When data is mostly sorted
• In situations where simplicity is more important than pure speed
• As a building block for more complex algorithms

While not the most efficient for large random datasets, Insertion Sort excels in scenarios where data is small or partially ordered, making it practically useful despite its O(n²) worst-case complexity.