In daily life, when we sort playing cards, we usually insert a newly drawn card into its correct position among the existing cards in our hand, keeping the cards in order at all times. This idea of “inserting one by one into the ordered part” is the core principle of the Insertion Sort algorithm.

Basic Idea of Insertion Sort¶

Insertion Sort is a simple and intuitive sorting algorithm. Its working principle is to insert elements of the array one by one into the sorted subarray, eventually making the entire array ordered. The specific steps are as follows:

1. Initial State: By default, the first element of the array is considered “sorted” (a single-element array is naturally ordered).
2. Process Subsequent Elements One by One: Start from the second element (index 1) and treat each element as a “to-be-inserted element”.
3. Find the Insertion Position: Compare the to-be-inserted element with the elements in the sorted subarray from back to front. Find the appropriate position and insert it, ensuring the subarray remains ordered after insertion.
4. Repeat the Process: Continue until all elements are inserted into their correct positions, and the sorting is complete.

Algorithm Implementation Steps¶

Taking the array [5, 2, 9, 1, 5, 6] as an example, let’s detail the insertion sort process:

1. Outer Loop: Traverse the array starting from the second element (index 1), and take the current to-be-inserted element as temp = arr[i].
2. Inner Loop: Start from the position before the current element (j = i-1) and compare with temp:
   - If the element in the sorted subarray arr[j] > temp, shift arr[j] one position to the right (arr[j+1] = arr[j]).
   - Continue comparing the previous element (j -= 1) until arr[j] <= temp or j < 0 (all elements are greater than temp).
3. Insert the Element: Insert temp at position j+1 (to ensure the subarray remains ordered after insertion).

Python Code Implementation¶

def insertion_sort(arr):
    # Outer loop: Start from the second element (index 1)
    for i in range(1, len(arr)):
        temp = arr[i]  # Save the current element to be inserted
        j = i - 1      # Start comparison from the end of the sorted subarray

        # Inner loop: Find the insertion position and shift elements
        while j >= 0 and arr[j] > temp:
            arr[j + 1] = arr[j]  # Shift current element right by one position
            j -= 1               # Compare the previous element

        arr[j + 1] = temp  # Insert temp into the correct position
    return arr

# Test code
if __name__ == "__main__":
    test_arr = [5, 2, 9, 1, 5, 6]
    print("Before sorting:", test_arr)
    sorted_arr = insertion_sort(test_arr)
    print("After sorting:", sorted_arr)

Code Execution Example¶

Taking [5, 2, 9, 1, 5, 6] as an example, let’s break down the sorting process step by step:

1. i=1 (to-be-inserted element=2):
   - temp=2, j=0, arr[0]=5>2 → arr[1]=5 (array becomes [5,5,9,1,5,6]), j=-1.
   - Insert temp at j+1=0 → array becomes [2,5,9,1,5,6].

2. i=2 (to-be-inserted element=9):
   - temp=9, j=1, arr[1]=5<=9 → loop terminates. Insert at j+1=2; array remains unchanged.

3. i=3 (to-be-inserted element=1):
   - temp=1, j=2, arr[2]=9>1 → arr[3]=9 (array becomes [2,5,9,9,5,6]), j=1.
   - arr[1]=5>1 → arr[2]=5 (array becomes [2,5,5,9,5,6]), j=0.
   - arr[0]=2>1 → arr[1]=2 (array becomes [2,2,5,9,5,6]), j=-1.
   - Insert temp at j+1=0 → array becomes [1,2,5,9,5,6].

4. Subsequent Steps: Continue processing remaining elements (5 and 6). The final array becomes [1,2,5,5,6,9].

Complexity Analysis¶

• Time Complexity:
• Best case (array is already sorted): O(n) (each element requires only one comparison).
• Worst case (array is reversed): O(n²) (each element requires n comparisons).
• Space Complexity: O(1) (only one temporary variable temp is used; in-place sorting).

Insertion Sort is suitable for small-scale data or nearly sorted data. It is simple to implement and stable. By understanding the core idea of “inserting one by one”, you can easily grasp the implementation logic of this classic sorting algorithm.