Insertion sort
What it is and why you might need it

General description

Insertion sort is a simple sorting algorithm that builds up the final sorted array element by element. For large arrays it is less efficient than more advanced algorithms such as quicksort, heapsort or merge sort. However, insertion sort also offers advantages.

Code example

// @param {array} unsorted array
function insertionSort(array) {
	// for each element ...
	for (let i = 0; i < array.length; i++) {
		// iterate reversed through array
		for (let j = i; j > 0; j--) {
			// if the current element is smaller -> swap
			if (array[j] < array[j - 1]) swap(array, j, j - 1);
		}
	}
	return array;
}

// basic swap function
function swap(array, indexA, indexB) {
	let temp = array[indexA];
	array[indexA] = array[indexB];
	array[indexB] = temp;
}

Explained

Basically, the insertion sort algorithm works by splitting an unsorted array into two parts (without actually creating a new array).

1. first a loop is initialized over all elements of the array.
2. for each iterator it is checked if the previous elements are smaller.
3. If the key element is smaller than the predecessor, it is compared with all elements before it. Thereby the elements are swapped in each case in case of a wrong order.

Use cases

It is a stable sorting algorithm. With a time complexity of O(n^2) it belongs to the slow sorting algorithms. It is suitable for arrays of small size, since it is very intuitive to implement.