easy

Implement Insertion Sort

Sort an array in place using the insertion sort algorithm.

1. Define the problem

Implement Insertion Sort

Given an integer array nums, sort it in non-decreasing order using insertion sort , without calling a built-in sort function. Grow the sorted prefix one value at a time: for each key, shift every bigger value in the sorted prefix one slot right, then drop the key into the gap it leaves behind.

Constraints

  • 1 ≤ nums.length ≤ 1000
  • -1000 ≤ numsi ≤ 1000

Example

Inputnums = [5, 2, 9, 1, 5, 6]
Output[1, 2, 5, 5, 6, 9]

Explanation Each value is inserted into its correct spot among the values already placed to its left.

2. Know the words first

In plain terms

Sorted prefix
The part of the array, starting at index 0, that is already in order.
Key
The next unsorted value, about to be inserted into the sorted prefix.
3. Visualize the solution

Grow the sorted prefix by inserting one key at a time

Grow the sorted prefix by inserting one key at a time
Statusinit

Sorted prefix: [5]. Key = 2.

What happens in this step

nums = [5, 2, 9, 1, 5, 6]
sorted prefix = [5], key = nums[1] = 2

A single value is trivially sorted. The next value, 2, becomes the key about to be inserted.
Step 1 of 5

Steps to visualize

  1. Start with a sorted prefix of length 1 — a single value is trivially sorted.
  2. Take the next value as the key.
  3. Shift every bigger value in the sorted prefix one slot right.
  4. Drop the key into the gap once a smaller value is found or the prefix start is reached.
  5. Repeat until every value has been inserted.
4. Walk through the code

Walk through the code

Same walkthrough, now with the code. Press Next to move one step and watch which lines run.

Grow the sorted prefix by inserting one key at a time
Statusinit

Sorted prefix: [5]. Key = 2.

What happens in this step

nums = [5, 2, 9, 1, 5, 6]
sorted prefix = [5], key = nums[1] = 2

A single value is trivially sorted. The next value, 2, becomes the key about to be inserted.
Step 1 of 5
5. Solution

Solution

solution.tsTypeScript
function insertionSort(nums) {
  for (let i = 1; i < nums.length; i++) {
    const key = nums[i];
    let j = i - 1;

    while (j >= 0 && nums[j] > key) {
      nums[j + 1] = nums[j];
      j--;
    }

    nums[j + 1] = key;
  }

  return nums;
}
Time
O(n^2)
Space
O(1)
6. Test cases

Test cases

InputExpectedCovers
nums = [5, 2, 9, 1, 5, 6][1, 2, 5, 5, 6, 9]example from the docstring
nums = [1, 2, 3, 4][1, 2, 3, 4]best case, no shifting needed at all
nums = [5, 4, 3, 2, 1][1, 2, 3, 4, 5]worst case, every key shifts past everything before it
nums = [7][7]smallest valid input, a single element
nums = [3, 1, 2, 3, 1][1, 1, 2, 3, 3]repeated values mixed throughout
nums = [-3, 5, -1, 0, -2][-3, -2, -1, 0, 5]negative and positive values mixed together

Keep reading