DEV Community

Cover image for Insertion Sort (JS Example)
Clean Code Studio
Clean Code Studio

Posted on • Updated on

Insertion Sort (JS Example)

Twitter Follow

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
Enter fullscreen mode Exit fullscreen mode

FAANG Study Resource: Cracking the Coding Interview
(Google Recommended)


My FAANG interview study notes

Insertion Sort Github

Clean Code

Top comments (1)

Collapse
 
cleancodestudio profile image
Clean Code Studio