---
# System prepended metadata

title: '#2 Insertion Sort'
tags: [Sort, Easy]

---

# #2 Insertion Sort

###### tags:`Sort` `Easy`

## Problem
Write a function that takes in an array of integers and returns a sorted
  version of that array. Use the Insertion Sort algorithm to sort the array.
  
If you're unfamiliar with Insertion Sort, we recommend watching the Conceptual
  Overview section of this question's video explanation before starting to code.

### Sample Input
```javascript
array = [8, 5, 2, 9, 5, 6, 3]
```

### Sample Output
```javascript
[2, 3, 5, 5, 6, 8, 9]
```
<br>

## Solutions

### Official 
```javascript=
// Best: O(n) time | O(1) space
// Average: O(n^2) time | O(1) space
// Worst: O(n^2) time | O(1) space
function insertionSort(array) {
  for (let i = 1; i < array.length; i++) {
    let j = i;
    while (j > 0 && array[j] < array[j - 1]) {
      swap(j, j - 1, array);
      j -= 1;
    }
  }
  return array;
}
function swap(i, j, array) {
  const temp = array[j];
  array[j] = array[i];
  array[i] = temp;
}
exports.insertionSort = insertionSort;
```
<br>

---

### Everyone's

:::spoiler 月
```javascript=
/* Time: O(n^2), Space O(1)
   n is the length of the array
*/
function insertionSort(array) {
    for(let i = 1; i < array.length; i++){
      let j = i;
      while(j > 0 && array[j] < array[j-1]){  
        [array[j-1], array[j]] = [array[j], array[j-1]];
        j--;
      }
    }
    return array
  }
```
:::

<br>

:::spoiler 東
```javascript=
// Time O(n^2) | Space O(1); n is the length of input array
function insertionSort(array) {
  if(array.length < 2) return array;
  for(let pointer = 1; pointer < array.length; pointer++) {
    const [currVal] = array.splice(pointer, 1);  // delete element
    if(currVal <= array[0]) array.unshift(currVal);
    else {
      for(let sortedArrIdx = pointer - 1; sortedArrIdx >= 0; sortedArrIdx--) {
        if(currVal > array[sortedArrIdx]) {
          array.splice(sortedArrIdx+1, 0, currVal);  // insert element
          break;
        }
      }
    }
  }
  return array;
}
```
:::

<br>

:::spoiler Hao
```javascript=
/**
 * Time complexity: O(n);
 * Space complexity: O(1);
 */

function insertionSort(array) {
    return array.reduce((acc, value) => {
        if (acc.length < 1) return [value];
        else {
            for (let i = 0; i < acc.length; i += 1) {
                if (value <= acc[i]) return [...acc.slice(0, i), value, ...acc.slice(i)];
                else if (i === acc.length - 1) return [...acc, value];
            }
        }
    }, []);
}
```
:::

<br>

:::spoiler YC
```javascript=
/*
  time: O(n^2) - where n is the length of the input array 
  space: O(1)
*/
function insertionSort(array) {
  for(let i = 1; i < array.length; i++){
    let j = i;
    while(array[j] < array[j - 1] && j > 0){
      [array[j], array[j - 1]] = [array[j - 1], array[j]];
      j--;
    }
  }

  return array;
}
```
:::

<br>


---

## Supplement / Discussion
https://visualgo.net/en/sorting