Implementing the Insertion Sort Algorithm in C++

Insertion sort is a simple and intuitive sorting algorithm whose core idea is to insert elements one by one into their appropriate positions in a sorted subarray (similar to sorting playing cards). The basic approach is: starting from the second element, take the current element, compare it with the previously sorted elements. If a previous element is larger, shift it backward until the insertion position is found. Insert the current element there and continue processing the next element. When implementing, an outer loop iterates through the elements, and an inner loop uses a temporary variable to save the current element. By comparing and shifting the previous elements to make space, the current element is finally inserted. The time complexity is O(n²) in the worst case and O(n) in the best case, with a space complexity of O(1). It is suitable for small-scale data or nearly sorted data. Its advantages include stability and simplicity, making it a foundation for understanding more complex sorting algorithms.