Summary of Insertion sort

## Understanding Insertion Sort Sorting is a fundamental operation in computer science, and there are many algorithms designed to arrange data in a specific order. One of the simplest and most intuitive of these is **Insertion Sort**. It's particularly useful for small datasets or when a list is already mostly sorted. > **Definition**: **Insertion Sort** is a sorting algorithm that builds a final sorted array one item at a time by repeatedly taking elements from the unsorted part and inserting them into their correct position in the sorted part. ### The Card Sorting Analogy Imagine you're playing cards and want to sort the hand you're holding. Typically, you'd pick up cards one by one from an unsorted pile. As you pick up each new card, you compare it with the cards you've already arranged in your hand (which are always kept sorted). You then slide the new card into its correct place, shifting other cards to make room. You repeat this until all cards are in your hand and sorted. This exact process is the core idea behind insertion sort. Insertion sort applies this logic to an array of numbers (or any comparable elements). It conceptually divides the array into two parts: a **sorted sub-array** and an **unsorted sub-array**. Initially, the very first element of the array is considered sorted, as a single element is always sorted by itself. ### How Insertion Sort Works: Step-by-Step Let's break down the process of insertion sort into clear steps: 1. **Initialization**: The algorithm begins by assuming the first element of the array, at index $0$, is already sorted. The rest of the elements, from index $1$ to $n-1$ (where $n$ is the total number of elements), form the unsorted part. 2. **Iterative Sorting**: The algorithm then iterates through the unsorted part, taking one element at a time and inserting it into the correct place in the sorted sub-array. a. **Select Key**: For each iteration, the current element being considered from the unsorted part is chosen. This element is often called the **key**. b. **Comparison and Shifting**: The key is then compared with elements in the sorted sub-array. This comparison happens from right to left, starting with the element immediately before the key and moving backwards towards the beginning of the array. c. **Find Position**: If an element in the sorted sub-array is found to be **greater than** the key, that element is shifted one position to the right. This action creates space for the key to be inserted later. d. **Insertion**: This shifting process continues until either an element smaller than or equal to the key is found, or the beginning of the array is reached. Once the correct spot is found (or made), the key is inserted into that position. 3. **Completion**: Steps $2a$ through $2d$ are repeated until all elements from the original array have been moved from the unsorted sub-array into the sorted sub-array, resulting in a fully sorted array. ### Detailed Example: Sorting `[5, 2, 4, 6, 1, 3]` Let's trace how insertion sort works with a specific array: **Initial Array**: $[5, 2, 4, 6, 1, 3]$ * **Step 1**: The first element, $5$, is considered sorted. The sorted part is $[5]$, and the unsorted part is $[2, 4, 6, 1, 3]$. We can visualize this as: $[5 \ | \ 2, 4, 6, 1, 3]$ (the bar separates sorted from unsorted). * **Step 2**: Take the next element from the unsorted part. Here, the **key** is $2$. * Compare $2$ with $5$. Since $2 < 5$, we shift $5$ one position to the right. * Array state: $[ \_ , 5 \ | \ 4, 6, 1, 3]$. * The beginning of the array is reached. Insert $2$ into the empty spot. * Sorted part: $[2, 5]$. Unsorted part: $[4, 6, 1, 3]$. * Array state: $[2, 5 \ | \ 4, 6, 1, 3]$. * **Step 3**: Take the next element from the unsorted part. Here, the **key** is $4$. * Compare $4$ with $5$. Since $4 < 5$, shift $5$ one position to the right. * Array state: $[2, \_ , 5 \ | \ 6, 1, 3]$.