Q21Data Structures

Insertion Sort is a fundamental, comparison-based sorting algorithm that physically mirrors the intuitive human approach to sorting a hand of playing cards. It is an "in-place" algorithm, meaning it requires minimal external memory space, and it is highly "stable," guaranteeing that identical duplicate elements will absolutely retain their original relative chronological order. While its overarching $O(n^2)$ time complexity renders it highly inefficient for massive datasets, its near $O(n)$ efficiency on nearly-sorted data and exceptionally low operational overhead make it the undisputed optimal algorithm for sorting very small, localized arrays.

1. Operational Methodology

The algorithm operates by conceptually dividing the single array into two distinct logical partitions: a "sorted" subarray occupying the left side, and an "unsorted" subarray occupying the right. Initially, the very first element (index 0) is arbitrarily considered the entirety of the sorted subarray. The algorithm then iterates through the remaining unsorted elements one by one. For each unsorted element, it temporarily extracts the value (calling it the "key"). It then systematically compares this key against the elements in the sorted left subarray, scanning from right to left. Any sorted element larger than the key is physically shifted one position to the right to create a physical gap. The key is finally inserted into this newly created, perfectly ordered gap.

2. Structural Algorithm

3. Step-by-Step Execution Trace

We will now rigorously trace the execution of this algorithm on the specifically provided array sequence: [68, 17, 26, 54, 77, 93, 31, 44, 55, 20].

• Initialization: The array is [68 | 17, 26, 54, 77, 93, 31, 44, 55, 20]. The pipe | denotes the conceptual boundary. 68 is considered sorted.
• Pass 1 (i=1, key=17): Compare 17 with 68. Since 68 > 17, shift 68 to the right. Insert 17. Array becomes: [17, 68 | 26, 54, 77, 93, 31, 44, 55, 20]
• Pass 2 (i=2, key=26): Compare 26 with 68. Shift 68. Compare 26 with 17. No shift. Insert 26. Array becomes: [17, 26, 68 | 54, 77, 93, 31, 44, 55, 20]
• Pass 3 (i=3, key=54): Compare 54 with 68. Shift 68. Compare 54 with 26. No shift. Insert 54. Array becomes: [17, 26, 54, 68 | 77, 93, 31, 44, 55, 20]
• Pass 4 (i=4, key=77): Compare 77 with 68. No shift needed. The element is already in place. Array becomes: [17, 26, 54, 68, 77 | 93, 31, 44, 55, 20]
• Pass 5 (i=5, key=93): Compare 93 with 77. No shift needed. Array becomes: [17, 26, 54, 68, 77, 93 | 31, 44, 55, 20]
• Pass 6 (i=6, key=31): This requires extensive shifting. Compare 31 with 93, 77, 68, 54. Shift all of them to the right. Compare with 26. No shift. Insert 31. Array becomes: [17, 26, 31, 54, 68, 77, 93 | 44, 55, 20]
• Pass 7 (i=7, key=44): Shift 93, 77, 68, 54. Insert 44. Array becomes: [17, 26, 31, 44, 54, 68, 77, 93 | 55, 20]
• Pass 8 (i=8, key=55): Shift 93, 77, 68. Insert 55. Array becomes: [17, 26, 31, 44, 54, 55, 68, 77, 93 | 20]
• Pass 9 (i=9, key=20): Shift 93, 77, 68, 55, 54, 44, 31, 26. Insert 20 immediately after 17. Array becomes: [17, 20, 26, 31, 44, 54, 55, 68, 77, 93 | ]

The primary loop terminates as the unsorted partition is now empty. The algorithm concludes, successfully yielding the fully sorted array: [17, 20, 26, 31, 44, 54, 55, 68, 77, 93].