Implementing the Insertion Sort Algorithm with Python

This paper introduces the insertion sort algorithm, whose core idea is to insert elements one by one into a sorted subarray, similar to the ordered insertion when organizing playing cards. The basic approach is: starting from the second element of the array, treat each element as an element to be inserted, compare it with the sorted subarray from the end to the beginning, find the appropriate position, and then insert it, ensuring the subarray remains ordered at all times. Taking the Python implementation as an example, the outer loop traverses the elements to be inserted (starting from index 1), and the inner loop uses a while loop to compare and shift elements backward. A temporary variable 'temp' is used to store the current element, which is finally inserted into the correct position. The code is an in-place sort that only uses one temporary variable, resulting in a space complexity of O(1). Time complexity: Best case (array already sorted) O(n), worst case (reverse order) O(n²); space complexity O(1). It is suitable for small-scale data or nearly sorted data, with simple implementation and stability.