Insertion Sort: How Does Insertion Sort Work? A Comparison with Bubble Sort

In programming, sorting is one of the most fundamental and commonly used operations. Whether processing student grades, product prices, or log data, sorting helps us organize information quickly. Today, we’ll explore two simple sorting algorithms: Insertion Sort and Bubble Sort, examining how they work and their differences.

Insertion Sort: The Art of “Inserting” One by One¶

The core idea of Insertion Sort is intuitive, like organizing a deck of cards—process each card from left to right and insert each new card into its correct position among the already sorted cards in hand. For example, with an unsorted array [5, 3, 8, 4, 2], the steps are as follows:

1. Initial State¶

Assume the first card 5 is already in hand (the “sorted portion”), and the remaining cards 3, 8, 4, 2 need to be inserted.

2. Insert the Second Card 3¶

• Compare 3 with the last card in the sorted portion (5): 3 < 5, so shift 5 right by one position to make space for 3.
• The sorted portion becomes [3, 5].

3. Insert the Third Card 8¶

• Compare 8 with the last card in the sorted portion (5): 8 > 5, so place it at the end.
• The sorted portion becomes [3, 5, 8].

4. Insert the Fourth Card 4¶

• Compare 4 with elements in the sorted portion from right to left:
• Compare with 8: 4 < 8 → shift 8 right;
• Compare with 5: 4 < 5 → shift 5 right;
• Compare with 3: 4 > 3 → found the correct position. Insert 4 to get [3, 4, 5, 8].

5. Insert the Fifth Card 2¶

• Compare 2 with elements in the sorted portion from right to left:
• Compare with 8: 2 < 8 → shift 8 right;
• Compare with 5: 2 < 5 → shift 5 right;
• Compare with 4: 2 < 4 → shift 4 right;
• Compare with 3: 2 < 3 → shift 3 right;
• Insert at the beginning. The final sorted array is [2, 3, 4, 5, 8].

Algorithm Summary:
Insertion Sort iterates from the second element onward. For each element key, it compares backward with the sorted portion, shifts elements right, and inserts key at the correct position. The pseudocode is:

for i from 1 to n-1:  // Start from the second element
    key = arr[i]
    j = i - 1       // Index of the last element in the sorted portion
    while j >= 0 and arr[j] > key:
        arr[j+1] = arr[j]  // Shift elements right
        j = j - 1
    arr[j+1] = key  // Insert key into its correct position

Bubble Sort: The “Adventure” of Adjacent Elements¶

Bubble Sort’s core idea is “compare adjacent elements and let the larger ones ‘bubble up’ to the end”. Imagine air bubbles rising in water: the largest bubble first reaches the surface (end of the array), followed by the second largest, until all elements are sorted.

Bubble Sort Example (Using [5, 3, 8, 4, 2]):¶

• First Pass: Compare adjacent elements from the start, bubbling larger elements to the end:
• 5 vs 3: 5 > 3 → swap → [3, 5, 8, 4, 2];
• 5 vs 8: 5 < 8 → no swap;
• 8 vs 4: 8 > 4 → swap → [3, 5, 4, 8, 2];

• 8 vs 2: 8 > 2 → swap → [3, 5, 4, 2, 8].
  After this pass, the largest element 8 is bubbled to the end.

• Second Pass: Process the first 4 elements (excluding the last 8):

• 3 vs 5: no swap;
• 5 vs 4: 5 > 4 → swap → [3, 4, 5, 2, 8];

• 5 vs 2: swap → [3, 4, 2, 5, 8].
  After this pass, the second largest element 5 is in place.

• Third Pass: Process the first 3 elements (excluding the last two):

• 3 vs 4: no swap;

• 4 vs 2: swap → [3, 2, 4, 5, 8].
  After this pass, the third largest element 4 is in place.

• Fourth Pass: Process the first 2 elements (excluding the last three):

• 3 vs 2: swap → [2, 3, 4, 5, 8].
  After this pass, the array is fully sorted.

Algorithm Summary:
Bubble Sort requires n-1 passes (where n is the array length). Each pass compares adjacent elements and ensures the largest unplaced element “bubbles” to its final position.

Insertion Sort vs Bubble Sort: Which is Better?¶

Conclusion¶

Both Insertion Sort and Bubble Sort are simple O(n²) algorithms, but Insertion Sort is more efficient in practice, especially for nearly sorted data. Bubble Sort is intuitive but involves more element swaps (each comparison may swap), while Insertion Sort only shifts elements once per insertion, reducing swap operations.

For beginners, understanding these two sorting methods (insertion vs. bubbling) is foundational for mastering more complex algorithms like Quick Sort or Merge Sort.