Insertion sort

insertion_sort.js

/**
 * Insertion sort.
 * O(n^2)
 */
const insertionSort = (arr) => {
	for(let i = 1; i < arr.length; i++) {
		let j = i;
		// const prev = arr[j-1];
		// const next = arr[j];
		// console.log(prev, next)
		// Keep moving the current item left while the previous is greater than the current
		while(j > 0 && arr[j-1] > arr[j]) {
			// Store the prev value to prevent loss when swapping
			const prev = arr[j-1];
				// Swap current value for item on the left
				arr[j-1] = arr[j];
				arr[j] = prev;
				console.log('arr', arr);
			j = j - 1;
		}
	}
	return arr;
}

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