Insertion Sort Explained: Efficiently Sorting Data

Insertion Sort

You’re interested in learning about Insertion Sort—another fundamental sorting algorithm that’s simple to understand and implement, right? Inspired by how people sort playing cards (inserting each card into its correct position in a sorted hand), Insertion Sort builds the final sorted array one element at a time. It’s especially efficient for small datasets or nearly sorted data, making it a practical choice for real-world scenarios like incremental data updates.

I. Core Principles of Insertion Sort

Insertion Sort follows a “build-a-sorted-array” approach, with three key steps:

Treat the first element as sorted: Start with the second element (index 1) as the first “unsorted” element.
Insert the current element into the sorted portion: For each unsorted element, compare it with elements in the sorted portion (to its left) and shift larger elements to the right.
Place the current element in its correct position: Once the correct position is found (where all elements to the left are smaller and all to the right are larger), insert the current element there.
Repeat: Move to the next unsorted element and repeat until the entire array is sorted.

Key Intuition

Imagine sorting a hand of cards: you pick the second card, compare it with the first (sorted) card, and insert it before or after. Then you pick the third card, compare it with the first two (now sorted), shift as needed, and insert—this is exactly how Insertion Sort works.

II. Complete Implementation Code (Python)

Below is a clear, optimized Insertion Sort implementation with detailed comments, including edge case handling and a reverse (descending) version:

python

运行

def insertion_sort(arr, ascending=True):
    """
    Insertion Sort: Sort the array in ascending or descending order
    :param arr: The list to be sorted (supports numeric types)
    :param ascending: If True, sort in ascending order; else, descending (default: True)
    :return: None (modifies the original array in-place)
    """
    n = len(arr)
    # Iterate through unsorted elements (start from index 1, since index 0 is "sorted")
    for i in range(1, n):
        current = arr[i]  # Current element to insert into the sorted portion
        j = i - 1         # Pointer for the sorted portion (starts at the end of sorted part)
        
        # Shift elements in the sorted portion to the right if they are out of order
        if ascending:
            # Ascending: shift elements > current to the right
            while j >= 0 and arr[j] > current:
                arr[j + 1] = arr[j]  # Shift right
                j -= 1               # Move pointer left
        else:
            # Descending: shift elements < current to the right
            while j >= 0 and arr[j] < current:
                arr[j + 1] = arr[j]  # Shift right
                j -= 1               # Move pointer left
        
        # Insert current element into its correct position
        arr[j + 1] = current

# Test cases
if __name__ == "__main__":
    # Test 1: Ordinary unordered array (ascending)
    test1 = [64, 34, 25, 12, 22, 11, 90]
    print("Ascending Sort - Before:", test1)
    insertion_sort(test1)
    print("Ascending Sort - After:", test1)  # Output: [11, 12, 22, 25, 34, 64, 90]

    # Test 2: Descending order
    test2 = [64, 34, 25, 12, 22, 11, 90]
    print("\nDescending Sort - Before:", test2)
    insertion_sort(test2, ascending=False)
    print("Descending Sort - After:", test2)  # Output: [90, 64, 34, 25, 22, 12, 11]

    # Test 3: Edge cases (empty array, single element, nearly sorted)
    test3 = []
    test4 = [42]
    test5 = [1, 3, 2, 4, 6, 5, 7]  # Nearly sorted
    insertion_sort(test3)
    insertion_sort(test4)
    insertion_sort(test5)
    print("\nEmpty array sorted:", test3)  # Output: []
    print("Single element sorted:", test4)  # Output: [42]
    print("Nearly sorted array:", test5)  # Output: [1, 2, 3, 4, 5, 6, 7]

    # Test 4: Array with duplicate elements
    test6 = [5, 3, 8, 3, 2, 7, 3]
    insertion_sort(test6)
    print("Array with duplicates sorted:", test6)  # Output: [2, 3, 3, 3, 5, 7, 8]

III. Key Code Explanations

Outer Loop (for i in range(1, n)):
- Starts at index 1 because the first element (index 0) is treated as the initial sorted portion.
- i iterates through all unsorted elements (from the second element to the end).
Current Element and Sorted Portion Pointer:
- current = arr[i]: Stores the element being inserted (preserves its value while shifting other elements).
- j = i - 1: Points to the last element of the sorted portion (starts just before the current element).
Shifting Elements:
- Ascending Order: The while loop shifts elements in the sorted portion to the right if they are larger than current (creates space for current).
- Descending Order: The loop shifts elements to the right if they are smaller than current.
- The loop stops when j goes out of bounds (start of the array) or a suitable position for current is found.
Insertion:
- arr[j + 1] = current: Places current in its correct position (right after the last element smaller than it, for ascending order).

IV. Algorithm Performance Analysis

Metric	Result	Explanation
Time Complexity (Best)	O(n)	When the array is already sorted (only 1 comparison per element, no shifts).
Time Complexity (Worst)	O(n²)	When the array is in reverse order (each element requires shifting all previous elements).
Time Complexity (Average)	O(n²)	Suitable for small datasets (n < 1000) or nearly sorted data.
Space Complexity	O(1)	In-place sorting—uses only a few temporary variables (no extra space for sub-arrays).
Stability	Stable	Equal elements retain their original relative order (no unnecessary swaps).

Why Insertion Sort Shines

Nearly Sorted Data: Achieves O(n) efficiency, outperforming Quick Sort/Merge Sort for data that’s already mostly ordered (e.g., real-time data streams where new elements are added to the end).
Small Datasets: Simple implementation and low constant factors make it faster than O(n log n) algorithms for small n (e.g., sorting a list of 100 elements).
In-Place & Stable: No extra memory needed, and preserves the order of equal elements—critical for sorting objects (e.g., sorting people by age while keeping same-age people in their original order).

V. Insertion Sort vs. Bubble Sort vs. Selection Sort

Feature	Insertion Sort	Bubble Sort	Selection Sort
Time Complexity (Best)	O(n)	O(n) (with optimization)	O(n²)
Number of Shifts/Swaps	Fewer (shifts are cheaper than swaps)	More (swaps are expensive)	1 swap per round
Stability	Stable	Stable	Unstable
Practical Efficiency (Small Data)	Fastest	Slowest (due to swaps)	Middle
Use Case	Nearly sorted data, small datasets	Educational purposes	Small datasets where swaps are costly