In C programming, how does the insertion sort algorithm build a sorted array from an unsorted array?

Introduction / Context:
Insertion sort is a simple sorting algorithm frequently introduced in basic algorithms and C programming courses. It is particularly easy to understand because its behaviour is similar to how many people sort playing cards in their hands: by inserting each new card into the correct position among the cards that are already in sorted order.

Given Data / Assumptions:

• An array of n elements needs to be sorted in ascending order.
• We are considering the standard insertion sort algorithm implemented with nested loops in C.
• The algorithm builds a sorted section of the array from left to right.

Concept / Approach:
Insertion sort maintains a prefix of the array that is already sorted. Initially, this sorted prefix contains only the first element. For each subsequent element at index i, the algorithm temporarily stores that key value, shifts any larger elements in the sorted prefix one position to the right, and then inserts the key into the correct gap. After each iteration, the sorted prefix grows by one element, until it covers the entire array.

Step-by-Step Solution:
Step 1: Treat the element at index 0 as a sorted subarray of length one.Step 2: For i from 1 to n - 1, set key = a[i] and j = i - 1.Step 3: While j is at least 0 and a[j] is greater than key, shift a[j] one position to the right into a[j + 1] and decrement j.Step 4: When you find the correct position, place key into a[j + 1].Step 5: Repeat until all elements have been inserted into the correct positions and the array is sorted.

Verification / Alternative check:
Consider the array [5, 2, 4]. After the first iteration with key 2, 5 is shifted to the right and 2 is inserted at index 0, giving [2, 5, 4]. After the next iteration with key 4, 5 is shifted to the right and 4 is inserted in the middle, giving [2, 4, 5]. This matches the description in option A.

Why Other Options Are Wrong:
Option B is describing quick sort, which partitions around a pivot instead of inserting into a sorted prefix.Option C describes selection sort, which finds the minimum each time rather than inserting into a sorted prefix.Option D describes merge sort, which builds the sorted array by merging sorted subarrays instead of inserting elements one by one.

Common Pitfalls:
Students sometimes mix up insertion and selection sort because both use nested loops. A good way to remember insertion sort is to focus on the shifting of elements to make room for the key, a behaviour that is not present in selection sort.

Final Answer:
The correct description is It builds the final sorted array by repeatedly taking the next element and inserting it into the correct position within the already sorted portion, shifting larger elements one position to the right.