Learn: Insertion Sort - How It Works

Welcome!Welcome back! You've already learned about bubble sort and how it works to sort data step-by-step. Today, we'll build on that knowledge and explore insertion sort, another method for arranging data in order.

What is Insertion Sort?Insertion sort is a simple sorting algorithm that builds a sorted list one item at a time. It compares each item with those already sorted and inserts it into its correct position.This is useful when you need to sort small data sets or when data is almost sorted.

How Does Insertion Sort Work?Insertion sort works by dividing the list into two parts: the sorted section and the unsorted section. Items from the unsorted section are moved into the correct position in the sorted section one by one.The process repeats until all items are sorted.

Key Steps of Insertion Sort1. Start with the first item in the list. This is considered sorted.2. Take the next item from the unsorted section and compare it to items in the sorted section.3. Shift larger items to the right and insert the new item into its correct position.4. Repeat until all items are sorted.

Why Is It Called 'Insertion' Sort?The algorithm is called insertion sort because each item from the unsorted section is inserted into its correct position in the sorted section.

Step-by-Step ExampleLet's look at how insertion sort works on a sample list: [8, 3, 5, 1]. We'll sort this in ascending order.

Review Time!Great work! You've learned how insertion sort works. Let's review the key points with a few questions.