👋
Welcome to my blog!

Insertion Sort

Grasp the method of insertion sort for organizing data with a straightforward, incremental approach.

Insertion Sort
Sorting
easy

Published At

6/4/2021

Reading Time

~ 2 min read

Write a function that takes in an array of integers and returns a sorted version of that array. Use the Insertion Sort algorithm to sort the array.

If you're unfamiliar with Insertion Sort, we recommend watching the Conceptual Overview section of this question's video explanation before starting to code.

Sample Input

js
array = [8, 5, 2, 9, 5, 6, 3]
js
array = [8, 5, 2, 9, 5, 6, 3]

Sample Output

js
[2, 3, 5, 5, 6, 8, 9]
js
[2, 3, 5, 5, 6, 8, 9]

Hints

Hint 1

Divide the input array into two subarrays in place. The first subarray should be sorted at all times and should start with a length of 1, while the second subarray should be unsorted. Iterate through the unsorted subarray, inserting all of its elements into the sorted subarray in the correct position by swapping them into place. Eventually, the entire array will be sorted.

Optimal Space & Time Complexity

Best: O(n) time | O(1) space - where n is the length of the input array Average: O(n^2) time | O(1) space - where n is the length of the input array Worst: O(n^2) time | O(1) space - where n is the length of the input array

Solution-1
js
function insertionSort(array) {
  for (let i = 1; i < array.length; i++) {
		let counter = i
		while (counter >= 0 && array[counter] < array[counter - 1]) {
			let temp = array[counter]
			array[counter] = array[counter - 1]
			array[counter - 1] = temp
			counter--;
		}
	}
	return array
}
Solution-1
js
function insertionSort(array) {
  for (let i = 1; i < array.length; i++) {
		let counter = i
		while (counter >= 0 && array[counter] < array[counter - 1]) {
			let temp = array[counter]
			array[counter] = array[counter - 1]
			array[counter - 1] = temp
			counter--;
		}
	}
	return array
}

🦔

Do you have any questions, or simply wish to contact me privately? Don't hesitate to shoot me a DM on Twitter.

Have a wonderful day.
Abhishek 🙏

Join My Exclusive Newsletter Community

Step into a world where creativity intersects with technology. By subscribing, you'll get a front-row seat to my latest musings, full-stack development resources, and exclusive previews of future posts. Each email is a crafted experience that includes:

  • In-depth looks at my covert projects and musings to ignite your imagination.
  • Handpicked frontend development resources and current explorations, aimed at expanding your developer toolkit.
  • A monthly infusion of inspiration with my personal selection of quotes, books, and music.

Embrace the confluence of words and wonder, curated thoughtfully and sent straight to your inbox.

No fluff. Just the highest caliber of ideas.