Insertion Sort

Insertion sort is a type of sort that can be used on any unsorted list. Insertion sort works by maintaining a sorted and unsorted sublist in the same array. Since one item is by definition sorted, the sorted list starts with one item. The leftmost item of the unsorted list is then inserted into the sorted list. If the item is being inserted into an array, then all prior items must be moved over by one before being inserted. Insertion sort takes `O(n^2)` time and requires `O(n)` space where `n` is the number of items in the array. This general concept for this sorting method has existed since long before computers, having been a common method to sort playing cards.

Code in JavaScript

				
function insertionSort(arr)
{
    for (let i = 1; i < arr.length; i++)
    {
        //save value to be inserted into sorted subarray
        insertVal = arr[i];
        //insert arr[i] into the sorted subarray arr[1..i-1]
        j = i - 1;
        while (j >= 0 && arr[j] > insertVal)
        {
            arr[j+1] = arr[j];
            j = j - 1;
        }    
        arr[j+1] = insertVal;
    }
    return arr;  
}
				
			

Interactive Sort Visualizer

This is an interactive demo for sorting. You can choose your own numbers to input for sorting, and it will create an image that can be saved in png format as well as output a plaintext version of the sorting steps shown in the image. You can perform the following actions with the visualizer:

• Choosing a sort from the drop-down: Switch the sort title, description, and code on this page.
• Pressing the sort button: Calculates or re-calculates the sort results to be displayed based on the sort selected in the drop-down box and the text in the input box. Results are displayed as both an image and plaintext.
• Pressing the save button: Saves the image of the sort steps.

Type in a list of comma separated integers (between -999 and 999) with or without spaces:

Ex 1: 2,-8,9,-54,-784,321,20

Ex 2: -5, 4, -7, 4, 87, 432, 678, 90, -45, -321