{"id":464,"date":"2025-06-29T20:08:29","date_gmt":"2025-06-29T14:38:29","guid":{"rendered":"https:\/\/codeanddebug.in\/blog\/?p=464"},"modified":"2025-06-29T20:08:30","modified_gmt":"2025-06-29T14:38:30","slug":"recursive-insertion-sort","status":"publish","type":"post","link":"https:\/\/codeanddebug.in\/blog\/recursive-insertion-sort\/","title":{"rendered":"Recursive Insertion Sort in Python"},"content":{"rendered":"\n

You\u2019re asked to sort an array using Insertion Sort<\/strong>, but instead of the classic iterative two-loop approach, you must implement it recursively in Python<\/strong>.<\/p>\n\n\n\n

Here’s the [Problem Link<\/span><\/mark><\/a><\/strong>] to begin with.<\/p>\n\n\n\n

Insertion Sort works by building the sorted portion of the array one element at a time: each new key is inserted into its correct place among the already-sorted elements to its left.<\/p>\n\n\n\n

Example<\/strong><\/p>\n\n\n\n

Input array<\/th>Output array<\/th><\/tr><\/thead>
[9, 5, 1, 4, 3]<\/code><\/td>[1, 3, 4, 5, 9]<\/code><\/td><\/tr><\/tbody><\/table><\/figure>\n\n\n\n

The recursive version mimics the \u201cexpand-then-insert\u201d logic by sorting the first n \u2013 1<\/code> elements recursively, then inserting the n<\/code>-th element (key<\/code>) into that sorted prefix.<\/p>\n\n\n

\n\t\t\t
\n\t\t\t\t
Contents:<\/div>\n\t\t\t\t
\n\t\t\t
\n\t\t\t\u00a0[show<\/a>]\n\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t<\/div>\n\t\t<\/div>
\n\t\t\t
\n\t\t\t\t