# Computer science in JavaScript: Insertion sort

Insertion sort is typically the third sorting algorithm taught in computer science programs, after bubble sort^{[1]} and selection sort^{[2]}. Insertion sort has a best-case complexity of O(n), which is less complex than bubble and selection sort at O(n^{2}). This is also the first stable sort algorithm taught.

Stable sort algorithms are sorts that don’t change the order of equivalent items in the list. In bubble and selection sort, it’s possible that equivalent items may end up in a different order than they are in the original list. You may be wondering why this matters if the items are equivalent. When sorting simple values, like numbers or strings, it is of no consequence. If you are sorting objects by a particular property, for example sorting `person`

objects on an `age`

property, there may be other associated data that should be in a particular order.

Sorting algorithms that perform swaps are inherently unstable. Items are always moving around and so you can’t guarantee any previous ordering will be maintained. Insertion sort doesn’t perform swaps. Instead, it picks out individual items and inserts them into the correct spot in an array.

An insertion sort works by separating an array into two sections, a sorted section and an unsorted section. Initially, of course, the entire array is unsorted. The sorted section is then considered to be empty. The first step is to add a value to the sorted section, so the first item in the array is used (a list of one item is always sorted). Then at each item in the unsorted section:

- If the item value goes after the last item in the sorted section, then do nothing.
- If the item value goes before the last item in the sorted section, remove the item value from the array and shift the last sorted item into the now-vacant spot.
- Compare the item value to the previous value (second to last) in the sorted section.
- If the item value goes after the previous value and before the last value, then place the item into the open spot between them, otherwise, continue this process until the start of the array is reached.

Insertion sort is a little bit difficult to explain in words. It’s a bit easier to explain using an example. Suppose you have the following array:

`var items = [5, 2, 6, 1, 3, 9];`

To start, the 5 is placed into the sorted section. The 2 then becomes the value to place. Since 5 is greater than 2, the 5 shifts over to the right one spot, overwriting the 2. This frees up a new spot at the beginning of the sorted section into which the 2 can be placed. See the figure below for a visualization of this process (boxes in yellow are part of the sorted section, boxes in white are unsorted).

The process then continues with 6. Each subsequent value in the unsorted section goes through the same process until the entire array is in the correct order. This process can be represented fairly succinctly in JavaScript as follows:

```
function insertionSort(items) {
var len = items.length, // number of items in the array
value, // the value currently being compared
i, // index into unsorted section
j; // index into sorted section
for (i=0; i < len; i++) {
// store the current value because it may shift later
value = items[i];
/*
* Whenever the value in the sorted section is greater than the value
* in the unsorted section, shift all items in the sorted section over
* by one. This creates space in which to insert the value.
*/
for (j=i-1; j > -1 && items[j] > value; j--) {
items[j+1] = items[j];
}
items[j+1] = value;
}
return items;
}
```

The outer `for`

loop moves from the front of the array towards the back while the inner loop moves from the back of the sorted section towards the front. The inner loop is also responsible for shifting items as comparisons happen. You can download the source code from my GitHub project, Computer Science in JavaScript.

Insertion sort isn’t terribly efficient with an average complexity of O(n^{2}). That puts it on par with selection sort and bubble sort in terms of performance. These three sorting algorithms typically begin a discussion about sorting algorithms even though you would never use them in real life. If you need to sort items in JavaScript, you are best off starting with the built-in `Array.prototype.sort()`

method before trying other algorithms. V8, the JavaScript engine in Chrome, actually uses insertion sort for sorting items with 10 or fewer items using `Array.prototype.sort()`

.

## References

Disclaimer: Any viewpoints and opinions expressed in this article are those of Nicholas C. Zakas and do not, in any way, reflect those of my employer, my colleagues, Wrox Publishing, O'Reilly Publishing, or anyone else. I speak only for myself, not for them.

Both comments and pings are currently closed.

## 7 Comments

Be aware the algorithm used by Array#sort() isn’t defined on the EcmaScript Spec and the behavior differs based on the browser and amount of items on the Array (v8 isn’t stable on “most” cases, Firefox/IE is). If you need a stable sort you still need to implement your own sorting. See these links for reference: http://code.google.com/p/v8/issues/detail?id=90 and https://bugzilla.mozilla.org/show_bug.cgi?id=224128

Miller Medeiros on September 17th, 2012 at 10:46 am

@Miller – Yep, I was going to get into that more when I discuss merge sort.

Nicholas C. Zakas on September 17th, 2012 at 10:50 am

Sorting – We’re Doing It Wrong…A couple of weeks ago it seemed my daily business became sorting DOMElements. This quickly became boring enough to be investigated more thoroughly. So this post sums up everything you should know about sorting DOMElements in Javascript (… using jQuery,…

Rodney Rehm on September 17th, 2012 at 11:44 am

But can you dance it out?

http://www.youtube.com/watch?v=ROalU379l3U

ken on September 17th, 2012 at 12:31 pm

[...] Computer science in JavaScript: Insertion sort (NCZOnline) [...]

Geek Reading September 18, 2012 | Regular Geek on September 18th, 2012 at 9:01 am

Bubble Sort also has a best case runtimes of O(n) and AVERAGE runtimes of O(n^2).

This is useful when you know something about the ordering of data that is going to be sorted (e.g. it’s coming into your function _almost_ in order and just needs a small touch-up). In that case you can use either Bubble Sort or Insertion Sort to quickly verify the order of the input without using much extra memory.

Alexander on September 19th, 2012 at 9:50 am

[...] An implementation in Javascript. A linked list of buffers in Node.js. A great set of implementations for Javascript. A computer science implementation of JavaScript. Also a nice insertion sort in Javascript. [...]

/dev/ – Linked List on September 20th, 2012 at 8:18 pm

Comments are automatically closed after 14 days.