Insertion Sort

  <ul style='text-align: left;list-style-type:disc; padding-left: 20px;'>
<li>Insertion Sort builds the final sorted array one item at a time.It takes an element from the unsorted part and inserts it into its correct position in the sorted part.</li>   
<li>While still O(n^2) in the worst case, Insertion Sort is efficient for small datasets and nearly sorted data. </li>  
</ul>

<pre style='text-align: left;'>

function insertionSort(arr) { let n = arr.length;

    for (let i = 1; i < n; i++) {
        let key = arr[i];
        let j = i - 1;

        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];
            j--;
       }


       arr[minIndex] = temp;
   }

  return arr;

const unsortedArray = [64, 34, 25, 12, 22, 11, 90]; const sortedArray = insertionSort(unsortedArray);