Skip to main content
Back to ChallengesImplement Insertion SortEasy 15 min

Implement Insertion Sort

Write a function that takes in an array of integers and returns a sorted version of that array using the Insertion Sort algorithm.

Insertion sort iterates, consuming one input element each repetition, and grows a sorted output list. At each iteration, it removes one element from the input data, finds the location it belongs within the sorted list, and inserts it there.

Examples

Input: arr = [8, 5, 2, 9, 5, 6, 3]
Output: [2, 3, 5, 5, 6, 8, 9]
The array is sorted in ascending order.

Constraints

  • • 1 <= arr.length <= 1000
  • • -10^4 <= arr[i] <= 10^4

Complexity Analysis

Time
O(N^2) worst case, but O(N) if the array is already sorted.
Space
O(1)
sorts in place.

Test Cases

#1 Standard unsorted array
Input: arr = [8,5,2,9,5,6,3]
Expected: [2,3,5,5,6,8,9]
#2 Single element
Input: arr = [5]
Expected: [5]
JavaScript
Output
Click "Run Code" to see output here...