Master insertion sort step by step. See how each element \u201cinserts\u201d into its correct place, watch a detailed dry run, and review commented Python code, intuition, and Big-O costs.<\/p>\n\n\n\n
So let’s get started with the [Problem Link<\/span><\/mark><\/a><\/strong>].<\/p>\n\n\n Insertion sort takes an array and builds the sorted<\/strong> list one item at a time, always keeping the left side already sorted.<\/p>\n\n\n\n Think about sorting a hand of playing cards:<\/p>\n\n\n\n That is exactly how insertion sort works on numbers.<\/p>\n\n\n\n Imagine a vertical divider<\/em> that separates the sorted<\/strong> left part from the unsorted<\/strong> right part.<\/p>\n\n\n\n1. What does the algorithm do?<\/h2>\n\n\n\n
\n
\n\n\n\n2. Quick examples<\/h2>\n\n\n\n
Input array<\/th> Sorted output<\/th> How it happens<\/th><\/tr><\/thead> [4, 3, 1, 2]<\/code><\/td>[1, 2, 3, 4]<\/code><\/td>4 \u2714 \u2192 insert 3 before 4 \u2192 insert 1 before 3 \u2192 insert 2 between 1 and 3<\/td><\/tr> [1, 2, 3, 4]<\/code><\/td>[1, 2, 3, 4]<\/code><\/td>Already sorted, each element stays in place (best case).<\/td><\/tr><\/tbody><\/table><\/figure>\n\n\n\n
\n\n\n\n3. Intuition & approach<\/h2>\n\n\n\n
3.1 Inner picture<\/h3>\n\n\n\n