# #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

array = [8, 5, 2, 9, 5, 6, 3]

### Sample Output

[2, 3, 5, 5, 6, 8, 9]

<br>

## Solutions

### Official

// 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 月

/* 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 東

// 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

/**
 * 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

/*
  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