AV
LibraryInsertion Sort

Insertion Sort

Easy

Insertion Sort 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.

Time Complexity

O(n²)

Space Complexity

O(1)

Category

Sorting

Introduction to Insertion Sort

Insertion Sort is a simple sorting algorithm that builds the final sorted array (or list) one item at a time. It is much less efficient on large lists than more advanced algorithms such as quicksort, heapsort, or merge sort.

How It Works

The algorithm works similarly to how you might sort playing cards in your hand:

1. Start with the second element (the first element is considered sorted)

2. Compare it with the elements before it

3. Shift elements greater than the key to the right

4. Insert the key in its correct position

5. Repeat for all elements

Algorithm Complexity

**Time Complexity**: O(n²) - In the worst case, we compare each element with all previous elements
**Space Complexity**: O(1) - Only requires a constant amount of additional space

Best and Worst Cases

**Best Case**: O(n) - When the array is already sorted
**Worst Case**: O(n²) - When the array is reverse sorted
**Average Case**: O(n²) - For random data

Advantages

1. Simple implementation

2. Efficient for small data sets

3. Adaptive (efficient for data sets that are already substantially sorted)

4. Stable sorting algorithm

5. In-place sorting

6. Online (can sort a list as it receives it)

Disadvantages

1. Inefficient for large lists

2. Performs more writes than Selection Sort

When to Use

**Small arrays**: Efficient for small number of elements
**Nearly sorted data**: Very fast if the input is nearly sorted
**Online sorting**: When data is coming in one by one

Comparison with Selection Sort

Insertion Sort is adaptive (faster if sorted), Selection Sort is not
Selection Sort makes fewer writes (O(n)), Insertion Sort makes O(n²) writes
Both have O(n²) time complexity

Key Takeaways

  • Builds sorted array one by one
  • Adaptive to sorted data
  • Stable sorting algorithm
  • In-place sorting
  • Efficient for small datasets

Implementation

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

Tags

sortingcomparisonsimplebeginner

Quick Stats

Difficulty:Easy
Type:Sorting

Share