Insertion Sort<\/strong><\/td>| O(n)<\/td> | O(n\u00b2)<\/td> | O(n\u00b2)<\/td> | O(1)<\/td> | Yes<\/td> | Small or nearly sorted arrays<\/td><\/tr> | | Bubble Sort<\/td> | O(n)<\/td> | O(n\u00b2)<\/td> | O(n\u00b2)<\/td> | O(1)<\/td> | Yes<\/td> | Educational use and very simple<\/td><\/tr> | | Selection Sort<\/td> | O(n\u00b2)<\/td> | O(n\u00b2)<\/td> | O(n\u00b2)<\/td> | O(1)<\/td> | No<\/td> | When swaps are more expensive than comparisons<\/td><\/tr> | | Merge Sort<\/td> | O(n log n)<\/td> | O(n log n)<\/td> | O(n log n)<\/td> | O(n)<\/td> | Yes<\/td> | Large datasets<\/td><\/tr> | | Quick Sort<\/td> | O(n log n)<\/td> | O(n log n)<\/td> | O(n\u00b2)<\/td> | O(log n)<\/td> | No<\/td> | Fastest in practice<\/td><\/tr><\/tbody><\/table>Comparison of Insertion Sort with Oher Sorting Algorithms<\/figcaption><\/figure>\n\n\n\n<\/span>Implementation of Insertion Sort in C++<\/strong><\/span><\/h2>\n\n\n\n#include <iostream>\r\nusing namespace std;\r\n\r\n\/\/ Function to perform insertion sort\r\nvoid insertionSort(int arr[], int n) {\r\n for (int i = 1; i < n; i++) {\r\n int key = arr[i];\r\n int j = i - 1;\r\n\r\n \/\/ Shift elements greater than key to the right\r\n while (j >= 0 && arr[j] > key) {\r\n arr[j + 1] = arr[j];\r\n j--;\r\n }\r\n\r\n arr[j + 1] = key;\r\n }\r\n}\r\n\r\n\/\/ Function to print the array\r\nvoid printArray(int arr[], int n) {\r\n for (int i = 0; i < n; i++)\r\n cout << arr[i] << \" \";\r\n cout << endl;\r\n}\r\n\r\n\/\/ Driver code\r\nint main() {\r\n int arr[] = {1, 7, 5, 12, 9, 6, 4, 2};\r\n int n = sizeof(arr) \/ sizeof(arr[0]);\r\n\r\n cout << \"Original array:\\n\";\r\n printArray(arr, n);\r\n\r\n insertionSort(arr, n);\r\n\r\n cout << \"Sorted array:\\n\";\r\n printArray(arr, n);\r\n\r\n return 0;\r\n}\r<\/code><\/pre>\n\n\n\n<\/span>Implementation of Insertion Sort in Python<\/strong><\/span><\/h2>\n\n\n\ndef insertion_sort(arr):\r\n # Traverse from 1 to len(arr)\r\n for i in range(1, len(arr)):\r\n key = arr[i]\r\n j = i - 1\r\n\r\n # Move elements of arr[0..i-1], that are greater than key, one position ahead\r\n while j >= 0 and arr[j] > key:\r\n arr[j + 1] = arr[j]\r\n j -= 1\r\n\r\n arr[j + 1] = key\r\n\r\n# Driver code\r\narr = [1, 7, 5, 12, 9, 6, 4, 2]\r\nprint(\"Original array:\")\r\nprint(arr)\r\n\r\ninsertion_sort(arr)\r\n\r\nprint(\"Sorted array:\")\r\nprint(arr)\r<\/code><\/pre>\n\n\n\n<\/span>Advantages of Insertion Sort Algorithm<\/strong><\/span><\/h2>\n\n\n\n\n- Simple to implement and understand.<\/li>\n\n\n\n
- Efficient for small or nearly sorted datasets.<\/li>\n\n\n\n
- In-place sorting with stable behavior.<\/li>\n<\/ol>\n\n\n\n
<\/span>Disadvantages of Insertion Sort Algorithm<\/strong><\/span><\/h2>\n\n\n\n\n- Insertion Sort is slow for large datasets because its time complexity is O(n\u00b2).<\/li>\n\n\n\n
- It is not ideal for large or completely unsorted data as it performs poorly in such cases.<\/li>\n\n\n\n
- It requires a lot of comparisons and shifting of elements in the worst case which makes it inefficient.<\/li>\n<\/ol>\n\n\n\n
<\/span>FAQs (Insertion Sort Algorithm)<\/strong><\/span><\/h2>\n\n\n\n<\/span>What is the insertion sort algorithm used for?<\/strong><\/span><\/h3>\n\n\n\nThe insertion sort algorithm is mainly used to sort small datasets or nearly sorted arrays. It’s a great choice when performance is not the top priority but simplicity and clarity are.<\/p>\n\n\n\n <\/span>Is insertion sort better than bubble sort?<\/strong><\/span><\/h3>\n\n\n\nYes, insertion sort usually performs better than bubble sort. It does fewer comparisons and swaps in practice, especially when the data is already partially sorted.<\/p>\n\n\n\n <\/span>Does insertion sort work in-place?<\/strong><\/span><\/h3>\n\n\n\nYes, insertion sort is an in-place sorting algorithm. It doesn\u2019t require any extra memory space and modifies the original array directly during the sorting process.<\/p>\n","protected":false},"excerpt":{"rendered":" Sorting is a common task in programming, and the insertion sort algorithm is one of the easiest ways to understand how sorting works. If you are just starting with algorithms or preparing for interviews then this guide is all you need to understand the insertion sort algorithm from the ground up. What is Insertion Sort […]<\/p>\n","protected":false},"author":560,"featured_media":48467,"comment_status":"closed","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[1075,1073],"tags":[],"yoast_head":"\n Insertion Sort Algorithm with Complexity Analysis - iQuanta<\/title>\n<meta name=\"description\" content=\"If you are just starting with algorithms or preparing for interviews then you need to understand the insertion sort algorithm.\" \/>\n<meta name=\"robots\" content=\"index, follow, max-snippet:-1, max-image-preview:large, max-video-preview:-1\" \/>\n<link rel=\"canonical\" href=\"https:\/\/www.iquanta.in\/blog\/insertion-sort-algorithm-with-complexity-analysis\/\" \/>\n<meta property=\"og:locale\" content=\"en_US\" \/>\n<meta property=\"og:type\" content=\"article\" \/>\n<meta property=\"og:title\" content=\"Insertion Sort Algorithm with Complexity Analysis\" \/>\n<meta property=\"og:description\" content=\"If you are just starting with algorithms or preparing for interviews then you need to understand the insertion sort algorithm.\" \/>\n<meta property=\"og:url\" content=\"https:\/\/www.iquanta.in\/blog\/insertion-sort-algorithm-with-complexity-analysis\/\" \/>\n<meta property=\"og:site_name\" content=\"iQuanta\" \/>\n<meta property=\"article:publisher\" content=\"https:\/\/facebook.com\/iquanta.in\" \/>\n<meta property=\"article:published_time\" content=\"2025-05-07T11:01:22+00:00\" \/>\n<meta property=\"article:modified_time\" content=\"2025-05-07T11:01:25+00:00\" \/>\n<meta property=\"og:image\" content=\"https:\/\/www.iquanta.in\/blog\/wp-content\/uploads\/2025\/05\/Your-paragraph-text-14.png\" \/>\n\t<meta property=\"og:image:width\" content=\"1600\" \/>\n\t<meta property=\"og:image:height\" content=\"900\" \/>\n\t<meta property=\"og:image:type\" content=\"image\/png\" \/>\n<meta name=\"author\" content=\"Nidhi Goswami\" \/>\n<meta name=\"twitter:card\" content=\"summary_large_image\" \/>\n<meta name=\"twitter:label1\" content=\"Written by\" \/>\n\t<meta name=\"twitter:data1\" content=\"Nidhi Goswami\" \/>\n\t<meta name=\"twitter:label2\" content=\"Est. reading time\" \/>\n\t<meta name=\"twitter:data2\" content=\"5 minutes\" \/>\n<script type=\"application\/ld+json\" class=\"yoast-schema-graph\">{\"@context\":\"https:\/\/schema.org\",\"@graph\":[{\"@type\":\"Article\",\"@id\":\"https:\/\/www.iquanta.in\/blog\/insertion-sort-algorithm-with-complexity-analysis\/#article\",\"isPartOf\":{\"@id\":\"https:\/\/www.iquanta.in\/blog\/insertion-sort-algorithm-with-complexity-analysis\/\"},\"author\":{\"name\":\"Nidhi Goswami\",\"@id\":\"https:\/\/www.iquanta.in\/blog\/#\/schema\/person\/ec8c8c25d0526dd86557b6fed064f7f3\"},\"headline\":\"Insertion Sort Algorithm with Complexity Analysis\",\"datePublished\":\"2025-05-07T11:01:22+00:00\",\"dateModified\":\"2025-05-07T11:01:25+00:00\",\"mainEntityOfPage\":{\"@id\":\"https:\/\/www.iquanta.in\/blog\/insertion-sort-algorithm-with-complexity-analysis\/\"},\"wordCount\":757,\"publisher\":{\"@id\":\"https:\/\/www.iquanta.in\/blog\/#organization\"},\"articleSection\":[\"DSA and Competitive Programming\",\"iSkills\"],\"inLanguage\":\"en-US\"},{\"@type\":\"WebPage\",\"@id\":\"https:\/\/www.iquanta.in\/blog\/insertion-sort-algorithm-with-complexity-analysis\/\",\"url\":\"https:\/\/www.iquanta.in\/blog\/insertion-sort-algorithm-with-complexity-analysis\/\",\"name\":\"Insertion Sort Algorithm with Complexity Analysis - iQuanta\",\"isPartOf\":{\"@id\":\"https:\/\/www.iquanta.in\/blog\/#website\"},\"datePublished\":\"2025-05-07T11:01:22+00:00\",\"dateModified\":\"2025-05-07T11:01:25+00:00\",\"description\":\"If you are just starting with algorithms or preparing for interviews then you need to understand the insertion sort algorithm.\",\"breadcrumb\":{\"@id\":\"https:\/\/www.iquanta.in\/blog\/insertion-sort-algorithm-with-complexity-analysis\/#breadcrumb\"},\"inLanguage\":\"en-US\",\"potentialAction\":[{\"@type\":\"ReadAction\",\"target\":[\"https:\/\/www.iquanta.in\/blog\/insertion-sort-algorithm-with-complexity-analysis\/\"]}]},{\"@type\":\"BreadcrumbList\",\"@id\":\"https:\/\/www.iquanta.in\/blog\/insertion-sort-algorithm-with-complexity-analysis\/#breadcrumb\",\"itemListElement\":[{\"@type\":\"ListItem\",\"position\":1,\"name\":\"Home\",\"item\":\"https:\/\/www.iquanta.in\/blog\/\"},{\"@type\":\"ListItem\",\"position\":2,\"name\":\"Insertion Sort Algorithm with Complexity Analysis\"}]},{\"@type\":\"WebSite\",\"@id\":\"https:\/\/www.iquanta.in\/blog\/#website\",\"url\":\"https:\/\/www.iquanta.in\/blog\/\",\"name\":\"iQuanta | Cat Preparation Online\",\"description\":\"Building Learning Networks\",\"publisher\":{\"@id\":\"https:\/\/www.iquanta.in\/blog\/#organization\"},\"potentialAction\":[{\"@type\":\"SearchAction\",\"target\":{\"@type\":\"EntryPoint\",\"urlTemplate\":\"https:\/\/www.iquanta.in\/blog\/?s={search_term_string}\"},\"query-input\":\"required name=search_term_string\"}],\"inLanguage\":\"en-US\"},{\"@type\":\"Organization\",\"@id\":\"https:\/\/www.iquanta.in\/blog\/#organization\",\"name\":\"IQuanta\",\"url\":\"https:\/\/www.iquanta.in\/blog\/\",\"logo\":{\"@type\":\"ImageObject\",\"inLanguage\":\"en-US\",\"@id\":\"https:\/\/www.iquanta.in\/blog\/#\/schema\/logo\/image\/\",\"url\":\"https:\/\/www.iquanta.in\/blog\/wp-content\/uploads\/2018\/08\/IQuanta-1.png\",\"contentUrl\":\"https:\/\/www.iquanta.in\/blog\/wp-content\/uploads\/2018\/08\/IQuanta-1.png\",\"width\":525,\"height\":200,\"caption\":\"IQuanta\"},\"image\":{\"@id\":\"https:\/\/www.iquanta.in\/blog\/#\/schema\/logo\/image\/\"},\"sameAs\":[\"https:\/\/facebook.com\/iquanta.in\"]},{\"@type\":\"Person\",\"@id\":\"https:\/\/www.iquanta.in\/blog\/#\/schema\/person\/ec8c8c25d0526dd86557b6fed064f7f3\",\"name\":\"Nidhi Goswami\",\"image\":{\"@type\":\"ImageObject\",\"inLanguage\":\"en-US\",\"@id\":\"https:\/\/www.iquanta.in\/blog\/#\/schema\/person\/image\/\",\"url\":\"https:\/\/secure.gravatar.com\/avatar\/21d234d87afd924b217d26b25a3cf1ee?s=96&d=mm&r=g\",\"contentUrl\":\"https:\/\/secure.gravatar.com\/avatar\/21d234d87afd924b217d26b25a3cf1ee?s=96&d=mm&r=g\",\"caption\":\"Nidhi Goswami\"},\"url\":\"https:\/\/www.iquanta.in\/blog\/author\/nidhigoswami\/\"}]}<\/script>\n<!-- \/ Yoast SEO Premium plugin. -->","yoast_head_json":{"title":"Insertion Sort Algorithm with Complexity Analysis - iQuanta","description":"If you are just starting with algorithms or preparing for interviews then you need to understand the insertion sort algorithm.","robots":{"index":"index","follow":"follow","max-snippet":"max-snippet:-1","max-image-preview":"max-image-preview:large","max-video-preview":"max-video-preview:-1"},"canonical":"https:\/\/www.iquanta.in\/blog\/insertion-sort-algorithm-with-complexity-analysis\/","og_locale":"en_US","og_type":"article","og_title":"Insertion Sort Algorithm with Complexity Analysis","og_description":"If you are just starting with algorithms or preparing for interviews then you need to understand the insertion sort algorithm.","og_url":"https:\/\/www.iquanta.in\/blog\/insertion-sort-algorithm-with-complexity-analysis\/","og_site_name":"iQuanta","article_publisher":"https:\/\/facebook.com\/iquanta.in","article_published_time":"2025-05-07T11:01:22+00:00","article_modified_time":"2025-05-07T11:01:25+00:00","og_image":[{"width":1600,"height":900,"url":"https:\/\/www.iquanta.in\/blog\/wp-content\/uploads\/2025\/05\/Your-paragraph-text-14.png","type":"image\/png"}],"author":"Nidhi Goswami","twitter_card":"summary_large_image","twitter_misc":{"Written by":"Nidhi Goswami","Est. reading time":"5 minutes"},"schema":{"@context":"https:\/\/schema.org","@graph":[{"@type":"Article","@id":"https:\/\/www.iquanta.in\/blog\/insertion-sort-algorithm-with-complexity-analysis\/#article","isPartOf":{"@id":"https:\/\/www.iquanta.in\/blog\/insertion-sort-algorithm-with-complexity-analysis\/"},"author":{"name":"Nidhi Goswami","@id":"https:\/\/www.iquanta.in\/blog\/#\/schema\/person\/ec8c8c25d0526dd86557b6fed064f7f3"},"headline":"Insertion Sort Algorithm with Complexity Analysis","datePublished":"2025-05-07T11:01:22+00:00","dateModified":"2025-05-07T11:01:25+00:00","mainEntityOfPage":{"@id":"https:\/\/www.iquanta.in\/blog\/insertion-sort-algorithm-with-complexity-analysis\/"},"wordCount":757,"publisher":{"@id":"https:\/\/www.iquanta.in\/blog\/#organization"},"articleSection":["DSA and Competitive Programming","iSkills"],"inLanguage":"en-US"},{"@type":"WebPage","@id":"https:\/\/www.iquanta.in\/blog\/insertion-sort-algorithm-with-complexity-analysis\/","url":"https:\/\/www.iquanta.in\/blog\/insertion-sort-algorithm-with-complexity-analysis\/","name":"Insertion Sort Algorithm with Complexity Analysis - iQuanta","isPartOf":{"@id":"https:\/\/www.iquanta.in\/blog\/#website"},"datePublished":"2025-05-07T11:01:22+00:00","dateModified":"2025-05-07T11:01:25+00:00","description":"If you are just starting with algorithms or preparing for interviews then you need to understand the insertion sort algorithm.","breadcrumb":{"@id":"https:\/\/www.iquanta.in\/blog\/insertion-sort-algorithm-with-complexity-analysis\/#breadcrumb"},"inLanguage":"en-US","potentialAction":[{"@type":"ReadAction","target":["https:\/\/www.iquanta.in\/blog\/insertion-sort-algorithm-with-complexity-analysis\/"]}]},{"@type":"BreadcrumbList","@id":"https:\/\/www.iquanta.in\/blog\/insertion-sort-algorithm-with-complexity-analysis\/#breadcrumb","itemListElement":[{"@type":"ListItem","position":1,"name":"Home","item":"https:\/\/www.iquanta.in\/blog\/"},{"@type":"ListItem","position":2,"name":"Insertion Sort Algorithm with Complexity Analysis"}]},{"@type":"WebSite","@id":"https:\/\/www.iquanta.in\/blog\/#website","url":"https:\/\/www.iquanta.in\/blog\/","name":"iQuanta | Cat Preparation Online","description":"Building Learning Networks","publisher":{"@id":"https:\/\/www.iquanta.in\/blog\/#organization"},"potentialAction":[{"@type":"SearchAction","target":{"@type":"EntryPoint","urlTemplate":"https:\/\/www.iquanta.in\/blog\/?s={search_term_string}"},"query-input":"required name=search_term_string"}],"inLanguage":"en-US"},{"@type":"Organization","@id":"https:\/\/www.iquanta.in\/blog\/#organization","name":"IQuanta","url":"https:\/\/www.iquanta.in\/blog\/","logo":{"@type":"ImageObject","inLanguage":"en-US","@id":"https:\/\/www.iquanta.in\/blog\/#\/schema\/logo\/image\/","url":"https:\/\/www.iquanta.in\/blog\/wp-content\/uploads\/2018\/08\/IQuanta-1.png","contentUrl":"https:\/\/www.iquanta.in\/blog\/wp-content\/uploads\/2018\/08\/IQuanta-1.png","width":525,"height":200,"caption":"IQuanta"},"image":{"@id":"https:\/\/www.iquanta.in\/blog\/#\/schema\/logo\/image\/"},"sameAs":["https:\/\/facebook.com\/iquanta.in"]},{"@type":"Person","@id":"https:\/\/www.iquanta.in\/blog\/#\/schema\/person\/ec8c8c25d0526dd86557b6fed064f7f3","name":"Nidhi Goswami","image":{"@type":"ImageObject","inLanguage":"en-US","@id":"https:\/\/www.iquanta.in\/blog\/#\/schema\/person\/image\/","url":"https:\/\/secure.gravatar.com\/avatar\/21d234d87afd924b217d26b25a3cf1ee?s=96&d=mm&r=g","contentUrl":"https:\/\/secure.gravatar.com\/avatar\/21d234d87afd924b217d26b25a3cf1ee?s=96&d=mm&r=g","caption":"Nidhi Goswami"},"url":"https:\/\/www.iquanta.in\/blog\/author\/nidhigoswami\/"}]}},"_links":{"self":[{"href":"https:\/\/www.iquanta.in\/blog\/wp-json\/wp\/v2\/posts\/48448"}],"collection":[{"href":"https:\/\/www.iquanta.in\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.iquanta.in\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.iquanta.in\/blog\/wp-json\/wp\/v2\/users\/560"}],"replies":[{"embeddable":true,"href":"https:\/\/www.iquanta.in\/blog\/wp-json\/wp\/v2\/comments?post=48448"}],"version-history":[{"count":8,"href":"https:\/\/www.iquanta.in\/blog\/wp-json\/wp\/v2\/posts\/48448\/revisions"}],"predecessor-version":[{"id":48468,"href":"https:\/\/www.iquanta.in\/blog\/wp-json\/wp\/v2\/posts\/48448\/revisions\/48468"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/www.iquanta.in\/blog\/wp-json\/wp\/v2\/media\/48467"}],"wp:attachment":[{"href":"https:\/\/www.iquanta.in\/blog\/wp-json\/wp\/v2\/media?parent=48448"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.iquanta.in\/blog\/wp-json\/wp\/v2\/categories?post=48448"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.iquanta.in\/blog\/wp-json\/wp\/v2\/tags?post=48448"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}
| |