Note: This is not a "professionally written" post. This is a post sharing personal notes I wrote down while preparing for FAANG interviews.
See all of my Google, Amazon, & Facebook interview study notes
Insertion Sort Breakdown
- Worst Complexity: n^2
- Average Complexity: n^2
- Best Complexity: n
- Space Complexity: 1
- Method: Insertion
- Stable: Yes
Insertion Sort Notes
Insertion sort is a simple sorting algorithm that builds the final sorted array one item at a time. It is much less efficient on large lists than more advanced algorithms such as quicksort, heapsort, or merge sort. Wikipedia
Insertion Sort JavaScript Implementation
const InsertionSort = (items = []) => {
for (let i = 1; i < items.length; i++)
{
let index = i-1
let temporary = items[i]
while (index >= 0 && items[index] > temporary)
{
items[index + 1] = items[index]
index--
}
items[index + 1] = temporary
}
return items
}
module.exports = InsertionSort
FAANG Study Resource: Cracking the Coding Interview
(Google Recommended)
Top comments (1)