Code of the day – Javascript Insertion Sort

Insertion Sort.
Best: O(n), Average: O(n²), Worst: O(n²)
Insertion sort is a simple sorting algorithm, a comparison sort in which the sorted array (or list) is built one entry at a time.
Visit Wikipedia for more information.

Code

//Programmer: Larry Battle Mar 9, 2011
//Purpose: Insertion sort implemented in Javascript.
var insertionSort = function (arr) {
    var len = arr.length, i = -1, j, tmp;

    while (len--) {
        tmp = arr[++i];
        j = i;
        while (j-- && arr[j] > tmp) {
            arr[j + 1] = arr[j];
        }
        arr[j + 1] = tmp;
    }
};

Usage

insertionSort( [5,4,3,2,1] ); //returns [1,2,3,4,5];
insertionSort( [ "bear", "dog", "cat" ] ) // returns ["bear", "cat", "dog"];

Demo

Jsbin.com
bateru.com/uploads

Here’s a great short video tutorial to help those clueless about insertion sort.


Update:

/**
* Sorts an array using insertion sort.
* 
* @param {Array} - arr
* @param {Boolean} areNumbers indicates whether the array elements should be cast as numbers.
* @return {Array} the sorted array.
*/
var insertionSort = function (arr, areNumbers) {
	arr = arr.concat();
	var len = arr.length,
	i = -1,
	j,
	tmp;
	while (len--) {
		tmp = arr[++i];
		j = i;
		while (j-- && areNumbers ? (+arr[j] > +tmp) : (arr[j] > tmp) ) {
			arr[j + 1] = arr[j];
		}
		arr[j + 1] = tmp;
	}
	return arr;
};

// Treat input as array of numbers
Input: insertionSort(["1","2","3","4","4","40","20","21"], true);
Output: ["1", "2", "3", "4", "4", "20", "21", "40"]

// Treat input as array of strings
Input: insertionSort(["1","2","3","4","4","40","20","21"]);
Output: ["1", "2", "20", "21", "3", "4", "4", "40"]