3. Insertion Sort.md

Insertion Sort

Insertion sort is a simple sorting algorithm that builds the final sorted array (or list) one item at a time. Much like Selection Sort, Insertion Sort also divides the input list into two parts (unsorted and sorted sublists). At each iteration, insertion sort removes one element from the unsorted input data, finds the location it belongs within the sorted list, and inserts it there. It repeats until no unsorted input elements remain. Insertion Sort also works similar to the way people sort playing cards in their hands.

Insertion Sort provides several advantages over the previous sorting algorithms:

• Adaptive; i.e., efficient for data sets that are already substantially sorted: the time complexity is O(kn) when each element in the input is no more than k places away from its sorted position
• Stable; i.e., does not change the relative order of elements with equal keys
• Online; i.e., can sort a list as it receives it

Time Complexity

• In the best case where the input array is already sorted, Insertion Sort has a O(n) time complexity. During each iteration, the first remaining element of the input is only compared with the right-most element of the sorted subsection of the array.
• Insertion Sort has a worst case time complexity of O(n²), which occurs when array is reverse sorted. In this case every iteration of the inner loop will scan and shift the entire sorted subsection of the array before inserting the next element.
• Insertion Sort also has an average time complexity of O(n²). However, Insertion Sort is one of the fastest algorithms for sorting very small arrays, even faster than Quicksort; Indeed, good Quicksort implementations use Insertion Sort for arrays smaller than a certain threshold.

Exercise

Write a function called insertionSort that takes an array of numbers, and returns the sorted array with all the numbers sorted from smallest to largest. Additionally, you should be able to see how the sorted values get "inserted" into their proper position for each pass.

Examples:

• Random

  insertionSort([9,0,7,3,4,6,8,2,1,5]) // [0,1,2,3,4,5,5,6,7,8,9]

• Nearly Sorted

  insertionSort([8,1,2,3,4,5,6,7]) // [1,2,3,4,5,5,6,7,8]

• Reversed

  insertionSort([9,8,7,6,5,4,3,2,1]) // [1,2,3,4,5,5,6,7,8,9]

• Few Unique

  insertionSort([4,5,2,4,5,1,3,5,4,5,3,5,3,2,4]) // [1,2,2,3,3,3,4,4,4,4,5,5,5,5,5]

Note: You should also see the status of the array after each pass in the console!

---

Solution

function insertionSort(arr) {
  //  Loop over the array starting at 2nd element
  for(let i = 1; i < arr.length; i++) {
    //  Store the current element in temp variable
    let temp = arr[i];
    //  Start an inner loop starting at current element, working backwards
    //  until a sorted position for the element is opened up
    for(var j = i; j > 0 && temp < arr[j - 1]; j--) arr[j] = arr[j - 1];
    //  Place the current element back into its sorted place
    arr[j] = temp;
  }
  //  Return the sorted array
  return arr;
}

References

Toptal - Insertion Sort Visualization

Wikipedia - Insertion Sort

GeeksforGeeks - Insertion Sort