Insertion Sort Algorithm in DSA Javascript - Cheat Sheet & Quick Revision

Recall & Review

beginner

What is the main idea behind the Insertion Sort algorithm?

Insertion Sort builds the final sorted list one item at a time by taking each element and inserting it into its correct position among the previously sorted elements.

beginner

How does Insertion Sort handle the elements during sorting?

It divides the list into a sorted and unsorted part. It takes elements from the unsorted part and inserts them into the correct position in the sorted part by shifting larger elements to the right.

intermediate

What is the worst-case time complexity of Insertion Sort and when does it occur?

The worst-case time complexity is O(n²), which happens when the input list is sorted in reverse order, causing maximum shifts for each insertion.

intermediate

Show the JavaScript code snippet for the core insertion step inside the Insertion Sort.

for (let j = i - 1; j >= 0 && arr[j] > key; j--) { arr[j + 1] = arr[j]; } arr[j + 1] = key;

beginner

Why is Insertion Sort efficient for nearly sorted or small lists?

Because it only shifts elements when necessary, so if the list is almost sorted, fewer shifts happen, making it run faster than more complex algorithms on small or nearly sorted data.

What does Insertion Sort do at each step?

A Swaps the first and last elements

B Inserts the current element into the correct position in the sorted part

C Divides the list into halves

D Finds the maximum element and places it at the end

Insertion Sort takes the current element and inserts it into the correct position among the sorted elements.

What is the best-case time complexity of Insertion Sort?

A O(n)

B O(n log n)

C O(n²)

D O(log n)

The best case is when the list is already sorted, so Insertion Sort only makes one pass with no shifts, resulting in O(n) time.

Which of these is true about Insertion Sort?

A It is the fastest sorting algorithm for large lists

B It always uses extra memory

C It is a stable sorting algorithm

D It sorts by dividing the list into two halves

Insertion Sort is stable because it does not change the relative order of equal elements.

In Insertion Sort, what happens when the current element is smaller than elements in the sorted part?

A Elements larger than the current element are shifted right

B The current element is discarded

C The list is reversed

D The current element is swapped with the last element

Elements larger than the current element are moved one position to the right to make space for insertion.

Which scenario causes the worst performance for Insertion Sort?

A List is empty

B List is already sorted

C List has all equal elements

D List is sorted in reverse order

When the list is sorted in reverse order, every element must be shifted, causing O(n²) time.

Explain how Insertion Sort works step-by-step on a small list.

Think about how you sort playing cards in your hand.

Describe the time complexity of Insertion Sort and when it performs best and worst.

Consider how many moves are needed depending on the order of elements.

Practice

1. What is the main idea behind the Insertion Sort algorithm?

easy

A. Build the sorted array one element at a time by inserting elements in the correct position

B. Divide the array into halves and sort each half separately

C. Swap adjacent elements if they are in the wrong order repeatedly

D. Select the smallest element and swap it with the first unsorted element

Solution

1. Step 1: Understand insertion sort process

   Insertion sort builds the sorted list by taking one element at a time and placing it in the correct position among the already sorted elements.

2. Step 2: Compare with other sorting methods

   Other options describe different algorithms: dividing (merge sort), swapping adjacent (bubble sort), selecting smallest (selection sort).

3. Final Answer:

   Build the sorted array one element at a time by inserting elements in the correct position -> Option A

4. Quick Check:

   Insertion sort = Insert elements step-by-step [OK]

Hint: Insertion sort inserts elements one by one in order [OK]

Common Mistakes:

• Confusing insertion sort with bubble sort
• Thinking it divides the array like merge sort
• Mixing it up with selection sort

2. Which of the following is the correct syntax to start the outer loop for insertion sort in JavaScript for an array arr?

easy

A. for(let i = 0; i < arr.length; i++)

B. for(let i = 1; i < arr.length; i++)

C. for(let i = arr.length - 1; i >= 0; i--)

D. for(let i = 0; i <= arr.length; i++)

Solution

1. Step 1: Identify starting index for insertion sort

   Insertion sort starts from the second element (index 1) because the first element is considered sorted.

2. Step 2: Check loop condition correctness

   The loop runs while i < arr.length to cover all elements. Starting at 0 or going beyond length is incorrect.

3. Final Answer:

   for(let i = 1; i < arr.length; i++) -> Option B

4. Quick Check:

   Start loop at 1 for insertion sort [OK]

Hint: Start outer loop at 1, not 0, in insertion sort [OK]

Common Mistakes:

• Starting loop at 0 instead of 1
• Using <= instead of < in loop condition
• Looping backwards incorrectly

3. What will be the output of the following JavaScript code?

function insertionSort(arr) {
  for(let i = 1; i < arr.length; i++) {
    let key = arr[i];
    let j = i - 1;
    while(j >= 0 && arr[j] > key) {
      arr[j + 1] = arr[j];
      j--;
    }
    arr[j + 1] = key;
  }
  return arr;
}

console.log(insertionSort([4, 2, 7, 1]));

medium

A. [2, 1, 4, 7]

B. [4, 2, 7, 1]

C. [1, 4, 2, 7]

D. [1, 2, 4, 7]

Solution

1. Step 1: Trace first iteration (i=1)

   key=2, compare with 4, shift 4 right, insert 2 at index 0 -> [2,4,7,1]

2. Step 2: Trace remaining iterations

   i=2: key=7, no shift -> [2,4,7,1]; i=3: key=1, shift 7,4,2 right, insert 1 at index 0 -> [1,2,4,7]

3. Final Answer:

   [1, 2, 4, 7] -> Option D

4. Quick Check:

   Sorted array = [1, 2, 4, 7] [OK]

Hint: Insertion sort outputs sorted array in ascending order [OK]

Common Mistakes:

• Not shifting elements correctly
• Returning original array without sorting
• Confusing key placement index

4. Find the error in this insertion sort code snippet:

function insertionSort(arr) {
  for(let i = 1; i <= arr.length; i++) {
    let key = arr[i];
    let j = i - 1;
    while(j >= 0 && arr[j] > key) {
      arr[j + 1] = arr[j];
      j--;
    }
    arr[j + 1] = key;
  }
  return arr;
}

medium

A. The outer loop condition should be i < arr.length instead of <=.

B. The inner while loop condition should be arr[j] < key.

C. The key should be assigned after the while loop, not before.

D. The variable j should start at i, not i - 1.

Solution

1. Step 1: Check outer loop boundary

   The loop runs from 1 to arr.length inclusive, but array indices go from 0 to arr.length - 1, so i < arr.length is correct.

2. Step 2: Verify other parts

   Inner loop condition and key assignment are correct; j starts at i - 1 to compare with previous elements.

3. Final Answer:

   The outer loop condition should be i < arr.length instead of <=. -> Option A

4. Quick Check:

   Loop must not exceed array length [OK]

Hint: Use i < arr.length to avoid out-of-bounds [OK]

Common Mistakes:

• Using <= causes index out of range error
• Changing inner loop condition incorrectly
• Misplacing key assignment

5. Given the array [3, 0, -2, 5, 1], after the second iteration (i=2) of insertion sort, what will the array look like?

hard

A. [0, 3, -2, 5, 1]

B. [0, -2, 3, 5, 1]

C. [-2, 0, 3, 5, 1]

D. [3, 0, -2, 5, 1]

Solution

1. Step 1: Trace first iteration (i=1)

   key=0, compare with 3, shift 3 right, insert 0 at index 0 -> [0,3,-2,5,1]

2. Step 2: Trace second iteration (i=2)

   key=-2, compare with 3 and 0, shift both right, insert -2 at index 0 -> [-2,0,3,5,1]

3. Final Answer:

   [-2, 0, 3, 5, 1] -> Option C

4. Quick Check:

   After 2 iterations, array is partially sorted [OK]

Hint: After i-th iteration, first i+1 elements are sorted [OK]

Common Mistakes:

• Not shifting all larger elements
• Inserting key at wrong position
• Confusing iteration count with index