Insertion Sort Implementation

Medium~15 min

Implement insertion sort from scratch.

Given an array of integers nums, sort it in ascending order using the insertion sort algorithm and return the sorted array.

Insertion sort works by building a sorted portion of the array one element at a time. For each element, it finds the correct position in the already-sorted portion and inserts it there by shifting elements to the right.

Do not use any built-in sort functions.

Examples

Example 1
Input: nums = [5, 2, 4, 6, 1, 3]
Output: [1, 2, 3, 4, 5, 6]
Explanation: Each element is inserted into its correct position in the sorted portion: 5 → [2,5] → [2,4,5] → [2,4,5,6] → [1,2,4,5,6] → [1,2,3,4,5,6].
Example 2
Input: nums = [3, 1, 2]
Output: [1, 2, 3]
Explanation: Start with 3. Insert 1 before 3: [1,3]. Insert 2 between 1 and 3: [1,2,3].
Example 3
Input: nums = [1]
Output: [1]
Explanation: A single element is already sorted.

Constraints

  • 1 <= nums.length <= 1000
  • -10^4 <= nums[i] <= 10^4
  • You must implement insertion sort (do not use built-in sort)
Code
Ctrl+EnterRun|Ctrl+⇧+EnterSubmit
Output

Run your code to see results

Use Cmd+Enter to run