Coding

Insertion Sorting

Asked at

Amazon

1Give yourself 5 minutes

2Answer out loud, not in your head

3Then compare with the answer below

The problem

Given an array of integers called nums, sort the array in non-decreasing order using the insertion sort algorithm and return the sorted array.

A sorted array in non-decreasing order is an array where each element is greater than or equal to all preceding elements in the array.

**Input: **nums = [7, 4, 1, 5, 3] Output: [1, 3, 4, 5, 7] Explanation: 1 <= 3 <= 4 <= 5 <= 7. Thus the array is sorted in non-decreasing order.

**Input: **nums = [5, 4, 4, 1, 1] Output: [1, 1, 4, 4, 5] Explanation: 1 <= 1 <= 4 <= 4 <= 5. Thus the array is sorted in non-decreasing order.

Input: nums = [3, 2, 3, 4, 5]

1 <= nums.length <= 1000
-104 <= nums[i] <= 104
nums[i] may contain duplicate values.

cpp

class Solution {
public:
    vector<int> insertionSort(vector<int>& nums) {

    }
};

java

class Solution {
    public int[] insertionSort(int[] nums) {

    }
}

python

class Solution:
    def insertionSort(self, nums):

javascript

class Solution {
    insertionSort(nums) {

    }
}

csharp

public class Solution {
    public int[] InsertionSort(int[] nums) {
    
    }
}

func insertionSort(nums []int) []int {
    //your code goes here
}

Stuck? Show a way to structure it+

01Treat the first element as a sorted prefix.
02Take the next value as key.
03Shift larger prefix values right.
04Insert key into the created gap.
05Repeat through the array.

Reference answer

Maintain the invariant that the subarray before index i is sorted. For each i from one onward, save nums[i] as key and move j left through the sorted prefix. While j is valid and nums[j] is greater than key, shift nums[j] one position right. Once the correct gap is found, write key there. Using greater-than rather than greater-than-or-equal preserves stability: equal elements keep their original relative order. Walk through a nearly sorted example to show that shifting stops quickly. The best case is O(n) time when input is already sorted; average and worst cases are O(n squared) because many shifts occur. The algorithm is in place with O(1) extra space. Do not call a library sort, since the task specifically evaluates the insertion-sort mechanism.

Then expect these follow-ups

Why is insertion sort stable?
Tests: correctness reasoning
When is insertion sort preferable to merge sort?
Tests: follow-up reasoning

Free to read · better with Enzo

Practice this out loud with Enzo

Enzo runs it as a mock interview, pushes back with follow-ups, and grades you on the rubric.

Continue with Enzo Sign up free

Next question