{"id":9768,"date":"2025-08-29T15:51:15","date_gmt":"2025-08-29T10:21:15","guid":{"rendered":"https:\/\/namastedev.com\/blog\/?p=9768"},"modified":"2025-10-22T20:28:42","modified_gmt":"2025-10-22T14:58:42","slug":"insertionsort","status":"publish","type":"post","link":"https:\/\/namastedev.com\/blog\/insertionsort\/","title":{"rendered":"Insertion Sort"},"content":{"rendered":"\n<!-- Sum of all numbers in array using Recursion 1 -->\n<link\n    href=\"https:\/\/cdn.jsdelivr.net\/npm\/prismjs@1.29.0\/themes\/prism-tomorrow.min.css\"\n    rel=\"stylesheet\"\n\/>\n<script src=\"https:\/\/cdn.jsdelivr.net\/npm\/prismjs@1.29.0\/prism.min.js\"><\/script>\n<script src=\"https:\/\/cdn.jsdelivr.net\/npm\/prismjs@1.29.0\/plugins\/autoloader\/prism-autoloader.min.js\"><\/script>\n\n<style>\n.wp_blog_theme {\n  --primary: #E58C32;\n  --secondary: #030302;\n  --light-bg: #fef9f4;\n  --text-dark: #2d2d2d;\n  --tab-radius: 12px;\n  --shadow: 0 4px 12px rgba(0, 0, 0, 0.08);\n  --code-bg: #001f3f;\n  --code-text: #d4f1ff;\n}\n\n.wp_blog_container {\n  font-family: 'Segoe UI', sans-serif;\n  background: var(--light-bg);\n  margin: 0;\n  padding: 0;\n  color: var(--text-dark);\n}\n\n\/* Heading *\/\n.wp_blog_main-heading {\n  text-align: center;\n  font-size: 2.4rem;\n  color: var(--primary);\n  margin-top: 2.5rem;\n  font-weight: bold;\n}\n\n\/* Explanation Card *\/\n.wp_blog_explanation,\n.wp_blog_code-tabs-container {\n  max-width: 940px;\n  margin: 2rem auto;\n  padding: 2rem;\n  background: white;\n  border-radius: var(--tab-radius);\n  box-shadow: var(--shadow);\n}\n\n\/* Text and Visuals *\/\n.wp_blog_explanation h2 {\n  font-size: 1.4rem;\n  color: var(--primary);\n  margin-bottom: 0.5rem;\n}\n\n.wp_blog_explanation p,\n.wp_blog_explanation li {\n  font-size: 1.05rem;\n  line-height: 1.7;\n  margin: 0.5rem 0;\n}\n\n.wp_blog_explanation code {\n  background: #fef9f4;   \/* light bg instead of dark blue *\/\n  color: #E58C32;        \/* brand orange *\/\n  padding: 3px 6px;\n  border-radius: 4px;\n  font-family: 'Courier New', monospace;\n  font-weight: 600;      \/* optional, makes it pop *\/\n}\n\n.wp_blog_explanation img {\n  max-width: 100%;\n  border-radius: var(--tab-radius);\n  margin-top: 1rem;\n  box-shadow: 0 2px 12px rgba(0, 0, 0, 0.06);\n}\n\n\/* Tab Buttons *\/\n.wp_blog_code-tabs-header {\n  display: flex;\n  flex-wrap: wrap;\n  gap: 0.5rem;\n  margin-bottom: 1rem;\n}\n\n.wp_blog_code-tab-button {\n  padding: 0.6rem 1.2rem;\n  border: 1px solid var(--primary);\n  background: white;\n  color: var(--primary);\n  border-radius: 50px;\n  font-weight: 600;\n  cursor: pointer;\n  transition: all 0.3s ease;\n}\n\n.wp_blog_code-tab-button:hover {\n  background: var(--secondary);\n}\n\n.wp_blog_code-tab-button.active {\n  background: var(--primary);\n  color: white;\n}\n\n\/* Code Content *\/\n.wp_blog_code-tab-content {\n  display: none;\n  background: var(--code-bg);\n  border-radius: var(--tab-radius);\n}\n\n.wp_blog_code-tab-content.active {\n  display: block;\n}\n\n.wp_blog_code-tab-content pre {\n  margin: 0;\n  padding: 1.5rem;\n  font-size: 1rem;\n  overflow-x: auto;\n  background: var(--code-bg);\n  border-radius: var(--tab-radius);\n  color: var(--code-text);\n}\n\n\/* Dark mode variables *\/\n.wp_blog_theme.dark-mode {\n  --light-bg: #121212;\n  --text-dark: #f5f5f5;\n  --shadow: 0 4px 12px rgba(255, 255, 255, 0.08);\n  --code-bg: #1e1e1e;\n  --code-text: #c5f0ff;\n}\n\n.wp_blog_theme.dark-mode .wp_blog_explanation {\n  background: #1e1e1e;\n}\n\n\/* Dark mode code highlight *\/\n.wp_blog_theme.dark-mode .wp_blog_explanation code {\n  background: #333;\n  color: #ffd27f;\n}\n\n.wp_blog_theme {\n  position: relative; \/* makes it the reference for absolute children *\/\n}\n\n.wp_blog_toggle-btn {\n  position: absolute;\n  top: 1rem;\n  right: 1rem;\n  z-index: 9999;\n  padding: 0.5rem 0.8rem;\n  border-radius: 10%;\n  background: var(--primary);\n  color: white;\n  font-weight: bold;\n  cursor: pointer;\n  border: none;\n  box-shadow: var(--shadow);\n  transition: background 0.3s, transform 0.2s;\n}\n\n.wp_blog_toggle-btn:hover {\n  background: #cc772e;\n}\n\n.wp_blog_theme.dark-mode .wp_blog_code-tabs-container {\n  background: #1e1e1e;\n}\n<\/style>\n\n<div class=\"wp_blog_container wp_blog_theme\">\n        <button id=\"blogNotesThemeToggle\" class=\"wp_blog_toggle-btn\">\ud83c\udf19<\/button>\n\n<h1 class=\"wp_blog_main-heading\"><\/h1>\n\n<div class=\"wp_blog_explanation\">\n\n    <h2>Insertion Sort<\/h2>\n    <ul>\n        <li><strong>Insertion Sort is a simple and intuitive sorting algorithm<\/strong> that builds the final <code>sorted array one element<\/code> at a time.<\/li>\n        <li>It works by taking <strong>each element<\/strong> from the input and inserting it into its correct position in the <code>already sorted part of the array<\/code>. <\/li>\n        <li><code>Starting from the second element<\/code>, it compares the current element with the previous ones, <code>shifting larger elements<\/code> one position ahead to make space for the <strong>current element<\/strong>.<\/li>\n        <li>This <code>process continues<\/code> until all elements are <strong>sorted<\/strong>. <\/li>\n        <li> <code>Insertion Sort<\/code> is efficient for <code>small<\/code> or nearly <code>sorrted<\/code> datasets and operates in-place without requiring <strong>extra memory<\/strong>.<\/li>\n    <\/ul>\n    <!-- <h2>Example 1:<\/h2>\n    <p><strong>Input:<\/strong> [4, 5, 1, 3, 9]<\/p>\n    <p><strong>Output:<\/strong> [1, 3, 4, 5, 9]<\/p> -->\n\n    <!-- <h2>Example 2:<\/h2>\n    <p><strong>Input:<\/strong> arr = [6, 8, 0, 3]<\/p>\n    <p><strong>Output:<\/strong> -1<\/p>\n    <p><strong>Explanation: <\/strong>5 is not present in the array<\/p>\n -->\n\n    <h2>Approach:<\/h2>\n    <ul>\n        <li><code>Start from the second element<\/code> (index 1) since the first element is trivially <code>\u201csorted\u201d<\/code>.<\/li>\n        <li><strong>Store the current element<\/strong> (curr) and compare it with all <code>previous elements<\/code>.<\/li>\n        <li><code>Shift<\/code> the previous elements <strong>one position<\/strong> forward if they are greater than the current element.<\/li>\n        <li><code>Insert<\/code> the <strong>current element<\/strong> (curr) at its correct sorted position.<\/li>\n        <li><code>Repeat<\/code> until the whole <code>array is sorted<\/code>.<\/li>\n    <\/ul>\n\n    <h2>Time &#038; Space Complexity:<\/h2>\n    <p><strong>Time Complexity: O(n) <\/strong> Best Case <code>Already Sorted<\/code>.<\/p>\n    <p><strong>Average Case: <code>O(n<sup>2<\/sup>)<\/code><\/strong><\/p>\n    <p><strong>Worst Case: <code>O(n<sup>2<\/sup>)<\/code>Every element has to be compared and shifted back to the start.<\/strong><\/p>\n    <p><strong>Space Complexity: O(1)<\/strong>  No extra array is used; sorting is done in-place.<\/p>\n\n\n<h2>Dry Run<\/h2> \n<div style=\"background: var(--light-bg); border-left: 4px solid var(--primary); padding: 1rem; border-radius: var(--tab-radius); margin: 1rem 0; color: var(--text-dark);\"> \n  <p><strong>Input:<\/strong> <code>arr = [4, 5, 1, 3, 9]<\/code><\/p> \n\n  <pre style=\"white-space: pre-wrap; background: var(--code-bg); padding: 1rem; border-radius: 8px; overflow-x: auto; color: var(--code-text);\"> \ni = 1 \u2192 curr = 5, prev = 0\narr[0] = 4 \u2264 5 \u2192 no shifting\nInsert curr \u2192 [4, 5, 1, 3, 9]\n\ni = 2 \u2192 curr = 1, prev = 1\narr[1] = 5 > 1 \u2192 shift \u2192 [4, 5, 5, 3, 9]\narr[0] = 4 > 1 \u2192 shift \u2192 [4, 4, 5, 3, 9]\nprev = -1 \u2192 stop\nInsert curr \u2192 [1, 4, 5, 3, 9]\n\ni = 3 \u2192 curr = 3, prev = 2\narr[2] = 5 > 3 \u2192 shift \u2192 [1, 4, 5, 5, 9]\narr[1] = 4 > 3 \u2192 shift \u2192 [1, 4, 4, 5, 9]\narr[0] = 1 \u2264 3 \u2192 stop\nInsert curr \u2192 [1, 3, 4, 5, 9]\n\ni = 4 \u2192 curr = 9, prev = 3\narr[3] = 5 \u2264 9 \u2192 no shifting\nInsert curr \u2192 [1, 3, 4, 5, 9]\n\n<strong>Final Sorted Array:<\/strong> [1, 3, 4, 5, 9]\n  <\/pre> \n\n  <p><strong>Output:<\/strong> <code>[1, 3, 4, 5, 9]<\/code><\/p>\n<\/div>\n\n<\/div>\n\n\n<div class=\"wp_blog_code-tabs-container\">\n    <div class=\"wp_blog_code-tabs-header\">\n        <button class=\"wp_blog_code-tab-button active\" data-lang=\"js\">\n            JavaScript\n        <\/button>\n        <button class=\"wp_blog_code-tab-button\" data-lang=\"py\">Python<\/button>\n        <button class=\"wp_blog_code-tab-button\" data-lang=\"java\">Java<\/button>\n        <button class=\"wp_blog_code-tab-button\" data-lang=\"cpp\">C++<\/button>\n        <button class=\"wp_blog_code-tab-button\" data-lang=\"c\">C<\/button>\n        <button class=\"wp_blog_code-tab-button\" data-lang=\"cs\">C#<\/button>\n    <\/div>\n\n    <div class=\"wp_blog_code-tab-content active\" data-lang=\"js\">\n        <pre><code class=\"language-javascript\">\nlet arr = [4,5,1,3,9]\n  function insertionSort(arr){\n    let n = arr.length;\n    for(let i=1; i < n; i++) {\n      let curr = arr[i];\n      let prev = i - 1;\n      while(arr[prev] > curr && prev >= 0) {\n        arr[prev + 1] = arr[prev];\n        prev--;\n      }\n      arr[prev + 1] = curr;\n    }\n    return arr;\n  }\n  let result = insertionSort(arr);\n  console.log(\"Sorted array\", result);  \n      \n    <\/code><\/pre>\n    <\/div>\n    <div class=\"wp_blog_code-tab-content\" data-lang=\"py\">\n        <pre><code class=\"language-python\">\ndef insertionSort(arr):\n    n = len(arr)\n    for i in range(1, n):\n      curr = arr[i]\n      prev = i - 1\n      while prev >= 0 and arr[prev] > curr:\n        arr[prev + 1] = arr[prev]\n        prev -= 1\n      arr[prev + 1] = curr\n    return arr\n  \n  arr = [4, 5, 1, 3, 9]\n  print(\"Sorted array:\", insertionSort(arr))\n      \n    <\/code><\/pre>\n    <\/div>\n    <div class=\"wp_blog_code-tab-content\" data-lang=\"java\">\n        <pre><code class=\"language-java\">\npublic class Main {\n    public static void insertionSort(int[] arr) {\n      int n = arr.length;\n      for (int i = 1; i < n; i++) {\n        int curr = arr[i];\n        int prev = i - 1;\n        while (prev >= 0 && arr[prev] > curr) {\n          arr[prev + 1] = arr[prev];\n          prev--;\n        }\n        arr[prev + 1] = curr;\n      }\n    }\n  \n    public static void main(String[] args) {\n      int[] arr = {4, 5, 1, 3, 9};\n      insertionSort(arr);\n      System.out.println(\"Sorted array: \" + java.util.Arrays.toString(arr));\n    }\n  }\n<\/code><\/pre>\n    <\/div>\n    <div class=\"wp_blog_code-tab-content\" data-lang=\"cpp\">\n        <pre><code class=\"language-cpp\">\n#include &lt;iostream&gt;\n <!-- #include <iostream> -->\nusing namespace std;\n  \n  void insertionSort(int arr[], int n) {\n    for(int i = 1; i < n; i++) {\n      int curr = arr[i];\n      int prev = i - 1;\n      while(prev >= 0 && arr[prev] > curr) {\n        arr[prev + 1] = arr[prev];\n        prev--;\n      }\n      arr[prev + 1] = curr;\n    }\n  }\n  \n  int main() {\n    int arr[] = {4, 5, 1, 3, 9};\n    int n = sizeof(arr) \/ sizeof(arr[0]);\n    insertionSort(arr, n);\n    cout << \"Sorted array: \";\n    for(int i = 0; i < n; i++) cout << arr[i] << \" \";\n    return 0;\n  }   \n    <\/code><\/pre>\n    <\/div>\n\n    <div class=\"wp_blog_code-tab-content\" data-lang=\"c\">\n        <pre><code class=\"language-c\">\n#include &lt;stdio.h&gt;\n void insertionSort(int arr[], int n) {\n    for(int i = 1; i < n; i++) {\n      int curr = arr[i];\n      int prev = i - 1;\n      while(prev >= 0 && arr[prev] > curr) {\n        arr[prev + 1] = arr[prev];\n        prev--;\n      }\n      arr[prev + 1] = curr;\n    }\n  }\n  \n  int main() {\n    int arr[] = {4, 5, 1, 3, 9};\n    int n = sizeof(arr) \/ sizeof(arr[0]);\n    insertionSort(arr, n);\n    printf(\"Sorted array: \");\n    for(int i = 0; i < n; i++) printf(\"%d \", arr[i]);\n    return 0;\n  }\n   \n<\/code><\/pre>\n    <\/div>\n    <div class=\"wp_blog_code-tab-content\" data-lang=\"cs\">\n        <pre><code class=\"language-csharp\">\nusing System;\nclass Program\n{\n    static int[] InsertionSort(int[] arr)\n    {\n        int n = arr.Length;\n        for (int i = 1; i < n; i++)\n        {\n            int curr = arr[i];\n            int prev = i - 1;\n            \/\/ Shift elements greater than curr to one position ahead\n            while (prev >= 0 && arr[prev] > curr)\n            {\n                arr[prev + 1] = arr[prev];\n                prev--;\n            }\n            arr[prev + 1] = curr;\n        }\n        return arr;\n    }\n    static void Main(string[] args)\n    {\n        int[] arr = { 4, 5, 1, 3, 9 };\n        int[] result = InsertionSort(arr);\n        Console.WriteLine(\"Sorted array: \" + string.Join(\", \", result));\n    }\n}\n<\/code><\/pre>\n    <\/div>\n<\/div>\n<\/div>\n<script>\ndocument.addEventListener(\"DOMContentLoaded\", () => {\n  const buttons = document.querySelectorAll(\".wp_blog_code-tab-button\");\n  const contents = document.querySelectorAll(\".wp_blog_code-tab-content\");\n\n  buttons.forEach((button) => {\n    button.addEventListener(\"click\", () => {\n      const lang = button.getAttribute(\"data-lang\");\n\n      buttons.forEach((btn) => btn.classList.remove(\"active\"));\n      contents.forEach((content) => content.classList.remove(\"active\"));\n\n      button.classList.add(\"active\");\n      document\n        .querySelector(`.wp_blog_code-tab-content[data-lang=\"${lang}\"]`)\n        .classList.add(\"active\");\n    });\n  });\n\n  const themeToggle = document.getElementById(\"blogNotesThemeToggle\");\n  const themeContainer = document.querySelector(\".wp_blog_theme\");\n\n  themeToggle.addEventListener(\"click\", () => {\n    themeContainer.classList.toggle(\"dark-mode\");\n    themeToggle.textContent =\n      themeContainer.classList.contains(\"dark-mode\") ? \"\u2600\ufe0f\" : \"\ud83c\udf19\";\n  });\n});\n<\/script>\n","protected":false},"excerpt":{"rendered":"<p>\ud83c\udf19 Insertion Sort Insertion Sort is a simple and intuitive sorting algorithm that builds the final sorted array one element at a time. It works by taking each element from the input and inserting it into its correct position in the already sorted part of the array. Starting from the second element, it compares the<\/p>\n","protected":false},"author":108,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"om_disable_all_campaigns":false,"_monsterinsights_skip_tracking":false,"_monsterinsights_sitenote_active":false,"_monsterinsights_sitenote_note":"","_monsterinsights_sitenote_category":0,"footnotes":""},"categories":[210,322,176,175,174,172,173],"tags":[],"class_list":["post-9768","post","type-post","status-publish","format-standard","category-algorithms","category-algorithms-and-data-structures","category-csharp","category-cplusplus","category-java","category-javascript","category-python"],"aioseo_notices":[],"_links":{"self":[{"href":"https:\/\/namastedev.com\/blog\/wp-json\/wp\/v2\/posts\/9768","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/namastedev.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/namastedev.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/namastedev.com\/blog\/wp-json\/wp\/v2\/users\/108"}],"replies":[{"embeddable":true,"href":"https:\/\/namastedev.com\/blog\/wp-json\/wp\/v2\/comments?post=9768"}],"version-history":[{"count":4,"href":"https:\/\/namastedev.com\/blog\/wp-json\/wp\/v2\/posts\/9768\/revisions"}],"predecessor-version":[{"id":10546,"href":"https:\/\/namastedev.com\/blog\/wp-json\/wp\/v2\/posts\/9768\/revisions\/10546"}],"wp:attachment":[{"href":"https:\/\/namastedev.com\/blog\/wp-json\/wp\/v2\/media?parent=9768"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/namastedev.com\/blog\/wp-json\/wp\/v2\/categories?post=9768"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/namastedev.com\/blog\/wp-json\/wp\/v2\/tags?post=9768"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}