1. Starting with Sorting a Deck of Cards¶

Imagine you just received a shuffled deck of cards, for example: 5, 3, 8, 4, 2. Now you want to sort them in ascending order. How would you do it?

The most intuitive approach might be: First, pick a card (say the first one, 5) as your “sorted pile,” then take the remaining cards one by one and insert each into the correct position in the sorted pile.

• Step 1: Start with the first card, 5. Sorted pile: [5]
• Step 2: Take the second card, 3. Since 3 < 5, insert it before 5. Sorted pile becomes: [3, 5]
• Step 3: Take the third card, 8. Since 8 > 5, place it at the end of the sorted pile: [3, 5, 8]
• Step 4: Take the fourth card, 4. Compare with 8 (last element of the sorted pile): 4 < 8, so move 8 forward. Then compare with 5: 4 < 5, move 5 forward. Then compare with 3: 4 > 3, so insert between 3 and 5. Sorted pile becomes: [3, 4, 5, 8]
• Step 5: Take the fifth card, 2. Compare with 8, 5, 4, and 3. Since 2 is smaller than all, insert at the front. Final sorted pile: [2, 3, 4, 5, 8]

Is this process familiar? This is exactly the core idea of Insertion Sort—inserting each unsorted element into its correct position in the already sorted sequence.

2. Principles of Insertion Sort¶

Insertion Sort can be understood by the logic of “gradually building the sorted sequence”:

1. Default Order: Assume the first element is already part of the “sorted sequence” (a single element is trivially sorted).
2. Insert One by One: Starting from the second element, treat each element as a “new card” and insert it into the correct position in the previously sorted sequence.
3. Move Elements to Make Space: If the new card is smaller than some elements in the sorted sequence, shift those larger elements one position to the right to make space for the new card.

3. Example Demonstration: Using the Array [5, 3, 8, 4, 2]¶

Let’s simulate each step using array operations, based on the card-sorting example above:

Key Observation: When inserting, the element to be inserted is compared with elements in the sorted sequence from the end to the beginning until the correct position is found.

4. Algorithm Steps and Pseudocode¶

Algorithm Steps:¶

1. Traverse the array starting from the second element (index 1, denoted as i).
2. Store the current element arr[i] as key (the element to be inserted).
3. Start from the end of the sorted sequence (i.e., index i-1, denoted as j):
   - If arr[j] > key, shift arr[j] to the right (arr[j+1] = arr[j]).
   - If arr[j] <= key, stop shifting; the insertion position is j+1.
4. Insert key into position arr[j+1].
5. Continue processing the next element (i += 1) until all elements are sorted.

Pseudocode:¶

InsertionSort(arr)
    For i from 1 to length(arr) - 1:
        key = arr[i]  // Take the element to be inserted
        j = i - 1     // Index of the last element in the sorted sequence

        // Shift elements to the right until the correct position is found
        While j >= 0 and arr[j] > key:
            arr[j + 1] = arr[j]
            j = j - 1
        arr[j + 1] = key  // Insert the key into its correct position
    Return arr

5. Python Implementation¶

def insertion_sort(arr):
    # Traverse from the second element (index 1)
    for i in range(1, len(arr)):
        key = arr[i]  # Element to be inserted
        j = i - 1     # Index of the last element in the sorted part

        # Shift elements greater than key to the right
        while j >= 0 and key < arr[j]:
            arr[j + 1] = arr[j]
            j -= 1  # Move left to check the next element
        arr[j + 1] = key  # Insert the key into its correct position
    return arr

# Test the code
test_arr = [5, 3, 8, 4, 2]
sorted_arr = insertion_sort(test_arr)
print("Before sorting:", test_arr)
print("After sorting:", sorted_arr)

6. Characteristics of Insertion Sort¶

Advantages:¶

• Simple and Intuitive: Easy to understand and implement.
• In-place Sorting: Only requires a temporary variable (key), so space complexity is O(1).
• Adaptive: Efficient for “nearly sorted” data (e.g., already sorted arrays, time complexity approaches O(n)).
• Stable Sort: Preserves the relative order of equal elements (e.g., same-rank cards in a deck retain their original order).

Disadvantages:¶

• High Time Complexity: Worst-case (completely reversed) is O(n²), not suitable for large datasets.
• Many Shifts: For each element to be inserted, multiple elements in the sorted sequence may need to be shifted.

7. Summary¶

The core idea of Insertion Sort is like sorting a deck of cards: sort a small subset first, then gradually expand to the entire sequence. It is simple to implement, making it ideal for beginners to understand basic sorting concepts. It is also commonly used in practice for small datasets or nearly sorted data.

If you find the logic unclear, try manually simulating the sorting process with different arrays (e.g., [9, 7, 6, 15, 16, 5]) to solidify your understanding of “shifting sorted elements” and “finding the insertion position.” The foundation of sorting algorithms starts with these simple analogies!