{"id":6180,"date":"2025-05-29T19:21:24","date_gmt":"2025-05-29T13:51:24","guid":{"rendered":"https:\/\/namastedev.com\/blog\/?p=6180"},"modified":"2025-07-17T20:29:41","modified_gmt":"2025-07-17T14:59:41","slug":"insertion-sort","status":"publish","type":"post","link":"https:\/\/namastedev.com\/blog\/insertion-sort\/","title":{"rendered":"Insertion Sort"},"content":{"rendered":"\n<!-- Prism.js CSS and JS -->\n<link href=\"https:\/\/cdn.jsdelivr.net\/npm\/prismjs@1.29.0\/themes\/prism-tomorrow.css\" rel=\"stylesheet\" \/>\n<script src=\"https:\/\/cdn.jsdelivr.net\/npm\/prismjs@1.29.0\/prism.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_code-tabs-container {\n    font-family: \"Segoe UI\", sans-serif !important;\n    max-width: 900px !important;\n    margin: 2rem auto !important;\n    border: 1px solid #ddd !important;\n    border-radius: 8px !important;\n    overflow: hidden !important;\n    background-color: white !important;\n}\n\n.wp_blog_code-tabs-header {\n    background: #f7f7f7 !important;\n    display: flex !important;\n    border-bottom: 1px solid #ddd !important;\n}\n\n.wp_blog_code-tab-button {\n    flex: 1 !important;\n    padding: 10px 15px !important;\n    border: none !important;\n    background: transparent !important;\n    cursor: pointer !important;\n    font-weight: bold !important;\n    transition: background 0.2s !important;\n    color: #242B33 !important;\n}\n\n.wp_blog_code-tab-button.active {\n    background: white !important;\n    border-bottom: 3px solid #0073aa !important;\n}\n\n.wp_blog_code-tab-content {\n    display: none !important;\n    padding: 20px !important;\n    background: #242B33 !important;\n}\n\n.wp_blog_code-tab-content > pre {\n    background: #242B33 !important;\n}\n\n.wp_blog_code-tab-content.active {\n    display: block !important;\n}\n\n.wp_blog_code-tab-content pre {\n    margin: 0 !important;\n    overflow-x: auto !important;\n}\n\n.wp_blog_explanation {\n    max-width: 900px !important;\n    margin: 2rem auto !important;\n    font-family: \"Segoe UI\", sans-serif !important;\n    line-height: 1.6 !important;\n    background: white !important;\n    color: black !important;\n    padding: 1rem !important;\n    border-radius: 8px !important;\n}\n\n.wp_blog_explanation h2 {\n    color: #0073aa !important;\n    font-size: 1.5rem !important;\n    margin-bottom: 0.5rem !important;\n}\n\n.wp_blog_explanation code {\n    background: #f1f1f1 !important;\n    padding: 2px 6px !important;\n    border-radius: 4px !important;\n    font-family: monospace !important;\n}\n\n.wp_blog_explanation h1,\n.wp_blog_explanation h2,\n.wp_blog_explanation h3,\n.wp_blog_explanation h4,\n.wp_blog_explanation h5,\n.wp_blog_explanation h6,\n.wp_blog_explanation p {\n    margin-top: 10px !important;\n    margin-bottom: 10px !important;\n}\n<\/style>\n\n<!-- \u2705 START: Blog Explanation -->\n\n\n  <div class=\"wp_blog_explanation\">\n    <p>\n        <strong>Insertion Sort<\/strong> 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 current element with the previous ones, shifting larger elements one position ahead to make space for the current element. This process continues until all elements are sorted. Insertion Sort is efficient for small or nearly sorted datasets and operates in-place without requiring extra memory.\n      <\/p>\n      \n    <h2>Approach<\/h2>\n<ul>\n  <li>Start from the second element (index 1) since the first element is trivially &#8220;sorted&#8221;.<\/li>\n  <li>Store the current element (curr) and compare it with all previous elements.<\/li>\n  <li>Shift the previous elements one position forward if they are greater than the current element.<\/li>\n  <li>Insert the current element (curr) at its correct sorted position.<\/li>\n  <li>Repeat until the whole array is sorted.<\/li>\n<\/ul>\n\n<h2>Dry Run (on [4, 5, 1, 3, 9])<\/h2>\n<p><strong>Initial array:<\/strong><br>\n[4, 5, 1, 3, 9]<\/p>\n\n<p><strong>Pass 1 (i = 1):<\/strong><br>\ncurr = 5, prev = 0<\/p>\n<ul>\n  <li>5 > 4, no shifting \u2192 array remains [4, 5, 1, 3, 9]<\/li>\n<\/ul>\n\n<p><strong>Pass 2 (i = 2):<\/strong><br>\ncurr = 1, prev = 1<\/p>\n<ul>\n  <li>1 &lt; 5 \u2192 shift 5 \u2192 [4, 5, 5, 3, 9]<\/li>\n  <li>1 &lt; 4 \u2192 shift 4 \u2192 [4, 4, 5, 3, 9]<\/li>\n  <li>Insert 1 \u2192 [1, 4, 5, 3, 9]<\/li>\n<\/ul>\n\n<p><strong>Pass 3 (i = 3):<\/strong><br>\ncurr = 3, prev = 2<\/p>\n<ul>\n  <li>3 &lt; 5 \u2192 shift 5 \u2192 [1, 4, 5, 5, 9]<\/li>\n  <li>3 &lt; 4 \u2192 shift 4 \u2192 [1, 4, 4, 5, 9]<\/li>\n  <li>Insert 3 \u2192 [1, 3, 4, 5, 9]<\/li>\n<\/ul>\n\n<p><strong>Pass 4 (i = 4):<\/strong><br>\ncurr = 9, prev = 3<\/p>\n<ul>\n  <li>9 &gt; 5, no shifting \u2192 array remains [1, 3, 4, 5, 9]<\/li>\n<\/ul>\n\n<p><strong>Final Sorted Array:<\/strong><br>\n[1, 3, 4, 5, 9]<\/p>\n\n<h2>Time Complexity<\/h2>\n<ul>\n  <li><strong>Best Case (already sorted):<\/strong> O(n)<\/li>\n  <li><strong>Average Case:<\/strong> O(n\u00b2)<\/li>\n  <li><strong>Worst Case (reverse sorted):<\/strong> O(n\u00b2)<\/li>\n<\/ul>\n\n<h3>Why?<\/h3>\n<ul>\n  <li><strong>Best case:<\/strong> No shifting happens.<\/li>\n  <li><strong>Worst case:<\/strong> Every element has to be compared and shifted back to the start.<\/li>\n<\/ul>\n\n<h2>Space Complexity<\/h2>\n<ul>\n  <li>O(1) \u2192 No extra array is used; sorting is done in-place.<\/li>\n<\/ul>\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\">JavaScript<\/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=\"java\">Java<\/button>\n      <button class=\"wp_blog_code-tab-button\" data-lang=\"py\">Python<\/button>\n    <\/div>\n  \n    <div class=\"wp_blog_code-tab-content active\" data-lang=\"js\">\n      <pre><code class=\"language-javascript\">\n  let 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      <\/code><\/pre>\n    <\/div>\n  \n    <div class=\"wp_blog_code-tab-content\" data-lang=\"cpp\">\n      <pre><code class=\"language-cpp\">\n  #include &lt;iostream&gt;\n  using 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  \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      <\/code><\/pre>\n    <\/div>\n  \n    <div class=\"wp_blog_code-tab-content\" data-lang=\"java\">\n      <pre><code class=\"language-java\">\n  public 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  \n    <div class=\"wp_blog_code-tab-content\" data-lang=\"py\">\n      <pre><code class=\"language-python\">\n  def 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      <\/code><\/pre>\n    <\/div>\n  <\/div>\n  \n  \n  \n  \n  \n  \n<!-- \u2705 JS Tab Switch Logic -->\n<script>\ndocument.addEventListener('DOMContentLoaded', function () {\n    const buttons = document.querySelectorAll('.wp_blog_code-tab-button');\n    const contents = document.querySelectorAll('.wp_blog_code-tab-content');\n    buttons.forEach(button => {\n        button.addEventListener('click', () => {\n            const lang = button.getAttribute('data-lang');\n            buttons.forEach(btn => btn.classList.remove('active'));\n            button.classList.add('active');\n            contents.forEach(content => {\n                content.classList.toggle('active', content.getAttribute('data-lang') === lang);\n            });\n        });\n    });\n});\n<\/script>\n","protected":false},"excerpt":{"rendered":"<p>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 current element with<\/p>\n","protected":false},"author":1,"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":[811,810],"tags":[],"class_list":{"0":"post-6180","1":"post","2":"type-post","3":"status-publish","4":"format-standard","6":"category-data-structures-and-algorithms","7":"category-dsa"},"aioseo_notices":[],"_links":{"self":[{"href":"https:\/\/namastedev.com\/blog\/wp-json\/wp\/v2\/posts\/6180","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\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/namastedev.com\/blog\/wp-json\/wp\/v2\/comments?post=6180"}],"version-history":[{"count":2,"href":"https:\/\/namastedev.com\/blog\/wp-json\/wp\/v2\/posts\/6180\/revisions"}],"predecessor-version":[{"id":7983,"href":"https:\/\/namastedev.com\/blog\/wp-json\/wp\/v2\/posts\/6180\/revisions\/7983"}],"wp:attachment":[{"href":"https:\/\/namastedev.com\/blog\/wp-json\/wp\/v2\/media?parent=6180"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/namastedev.com\/blog\/wp-json\/wp\/v2\/categories?post=6180"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/namastedev.com\/blog\/wp-json\/wp\/v2\/tags?post=6180"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}