DSA Lesson 24 of 33

Insertion Sort

Learn how elements are inserted into their correct position.

Course Progress73%

Theory

Insertion Sort builds the sorted portion of an array one element at a time. Each new element is compared with previous elements and inserted into the correct position. It performs well on small or nearly sorted arrays.

Example

const numbers = [5, 3, 4, 1]; for (let i = 1; i < numbers.length; i++) { const key = numbers[i]; let j = i - 1; while (j >= 0 && numbers[j] > key) { numbers[j + 1] = numbers[j]; j--; } numbers[j + 1] = key; } console.log(numbers);

Expected Output

[1, 3, 4, 5]

Practice

Implement Insertion Sort and test it on an already sorted array.

Interview Questions

  1. How does Insertion Sort work?
  2. When is Insertion Sort efficient?
  3. What is its worst-case complexity?
  4. Is Insertion Sort stable?