# Insertion sort

## Definition

Insertion sort is a **simple sorting algorithm** that builds the final sorted array **one element at a time**. It uses **comparison** to find the correct position to insert the current element at, in order to maintain the sorted subarray.

## Implementation

- Use
`Array.prototype.reduce()`

to iterate over all the elements in the given array. - If the
`length`

of the accumulator is`0`

, add the current element to it. - Use
`Array.prototype.some()`

to iterate over the results in the accumulator until the correct position is found. - Use
`Array.prototype.splice()`

to insert the current element into the accumulator.

const insertionSort = arr => arr.reduce((acc, x) => { if (!acc.length) return [x]; acc.some((y, j) => { if (x <= y) { acc.splice(j, 0, x); return true; } if (x > y && j === acc.length - 1) { acc.splice(j + 1, 0, x); return true; } return false; }); return acc; }, []); insertionSort([6, 3, 4, 1]); // [1, 3, 4, 6]

## Complexity

The algorithm has an average time complexity of `O(n^2)`

, where `n`

is the size of the input array.