# Code of the day – Javascript Insertion Sort

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

## Code

 1 2 3 4 5 6 7 8 9 10 11 12 13 14 //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

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

## Demo

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"]
(Page view Count: 154)