Write a JavaScript function to implement the insertion sort algorithm that sorts an array of integers in ascending order. Explain your approach.

Background: The insertion sort algorithm is a simple sorting algorithm that works by picking an element and inserting it into its location before the elements that it is less than in order to get all of the numbers lined up in ascending order.

Example:

```
Input: [5, 2, 4, 6, 1, 3]
Output: [1, 2, 3, 4, 5, 6]
```

## Walkthrough

Solution Code:

```
function insertionSort(array) {
const length = array.length;
for (let i = 1; i < length; i++) {
const value = array[i];
let previous = i - 1;
while (previous >= 0 && array[previous] > value) {
array[previous + 1] = array[previous];
previous--;
}
array[previous + 1] = value;
}
return array;
}
```

Explanation:

We start by declaring a constant `length`

to store the length of the input array. Then, we loop through each element starting from the second element (index 1) by declaring a variable `i`

and setting it to 1.For each element, we store the value of the element in a constant `value`

and store the previous index in a variable `previous`

, which is initialized to `i - 1`

. We then enter a while loop that continues as long as `previous`

is greater than or equal to 0 and the element at `previous`

is greater than `value`

. Inside the while loop, we move the element at `previous`

to the right by setting the element at `previous + 1`

to the element at `previous`

. We then decrement `previous`

to check the previous element.Once we exit the while loop, we insert the value by setting the element at `previous + 1`

to `value`

. We repeat this process for each element in the input array, and then return the sorted array.**Big O Complexity Analysis:**
The time complexity of the insertion sort algorithm is O(n^2), where n is the number of elements in the array. This is because the algorithm involves nested loops. The outer loop iterates over each element in the array, and the inner loop may iterate over every previous element, resulting in a worst-case time complexity of O(n^2). The space complexity of the algorithm is O(1), since the algorithm sorts the array in place without creating any new arrays.