Insertion Sort

A corgi smiling happily

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

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

Sample Output

1[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

1function insertionSort(array) {
2 for (let i = 1; i < array.length; i++) {
3 let counter = i
4 while (counter >= 0 && array[counter] < array[counter - 1]) {
5 let temp = array[counter]
6 array[counter] = array[counter - 1]
7 array[counter - 1] = temp
8 counter--;
9 }
10 }
11 return array
12}

🦔

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 🙏

Subscribe to my newsletter

Get email from me about my ideas, full-stack development resources, tricks and tips as well as exclusive previews of upcoming articles.

No spam. Just the highest quality ideas you’ll find on the web.