A few sorting algorithms written in JavaScript.

``````/*
-----------------------------------------------------------------------------
Computer science in JavaScript: Selection sort
-----------------------------------------------------------------------------

article: http://www.nczonline.net/blog/2009/09/08/computer-science-in-javascript-selection-sort/
code: https://github.com/nzakas/computer-science-in-javascript/
*/

/**
* Swaps two values in an array.
*
* @param {Array} items The array containing the items.
* @param {int} firstIndex Index of first item to swap.
* @param {int} secondIndex Index of second item to swap.
* @return {void}
*/
function selectionSortSwap(items, firstIndex, secondIndex){
var temp = items[firstIndex];
items[firstIndex] = items[secondIndex];
items[secondIndex] = temp;
}

/**
* A selection sort implementation in JavaScript. The array
* is sorted in-place.
*
* @param {Array} items An array of items to sort.
* @return {Array} The sorted array.
*/
function selectionSort(items){

var len = items.length,
min, i, j;

for (i=0; i < len; i++){

// set minimum to this position
min = i;

// check the rest of the array to see if anything is smaller
for (j=i+1; j < len; j++){
if (items[j] < items[min]){
min = j;
}
}

// if the minimum isn't in the position, swap it
if (i != min){
selectionSortSwap(items, i, min);
}
}

return items;
}

/*
-----------------------------------------------------------------------------
Computer science in JavaScript: Quicksort
-----------------------------------------------------------------------------

article: http://www.nczonline.net/blog/2012/11/27/computer-science-in-javascript-quicksort/
code: https://github.com/nzakas/computer-science-in-javascript/
*/

/**
* Swaps two values in an array.
*
* @param {Array} items The array containing the items.
* @param {int} firstIndex Index of first item to swap.
* @param {int} secondIndex Index of second item to swap.
* @return {void}
*/
function quickSortSwap(items, firstIndex, secondIndex){
var temp = items[firstIndex];
items[firstIndex] = items[secondIndex];
items[secondIndex] = temp;
}

function partition(items, left, right) {

var pivot   = items[Math.floor((right + left) / 2)],  // pivot value is middle item
i       = left,     // starts from left and goes right to pivot index
j       = right;    // starts from right and goes left to pivot index

// while the two indices don't match
while (i <= j) {

// if the item on the left is less than the pivot, continue right
while (items[i] < pivot) {
i++;
}

// if the item on the right is greater than the pivot, continue left
while (items[j] > pivot) {
j--;
}

// if the two indices still don't match, swap the values
if (i <= j) {
quickSortSwap(items, i, j);

// change indices to continue loop
i++;
j--;
}
}

// this value is necessary for recursion
return i;
}

/**
* A quicksort implementation in JavaScript. The array
* is sorted in place.
*
* @param {Array} items An array of items to sort.
* @return {Array} The sorted array.
*/
function quickSort(items, left, right) {

var index;

// performance - don't sort an array with zero or one items
if (items.length > 1) {

// fix left and right values - might not be provided
left = typeof left != "number" ? 0 : left;
right = typeof right != "number" ? items.length - 1 : right;

// split up the entire array
index = partition(items, left, right);

// if the returned index
if (left < index - 1) {
quickSort(items, left, index - 1);
}

if (index < right) {
quickSort(items, index, right);
}

}

return items;
}

/*
-----------------------------------------------------------------------------
Computer science in JavaScript: Insertion sort
-----------------------------------------------------------------------------

article: http://www.nczonline.net/blog/2012/09/17/computer-science-in-javascript-insertion-sort/
code: https://github.com/nzakas/computer-science-in-javascript/
*/

/**
* An insertion sort implementation in JavaScript. The array
* is sorted in-place.
*
* @param {Array} items An array of items to sort.
* @return {Array} The sorted array.
*/
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;
}

/*
-----------------------------------------------------------------------------
Computer science in JavaScript: Merge sort
-----------------------------------------------------------------------------

article: http://www.nczonline.net/blog/2012/10/02/computer-science-and-javascript-merge-sort/
code: https://github.com/nzakas/computer-science-in-javascript/
*/

/*
* Iterative merge sort implementation in JavaScript
* Copyright (c) 2009-2011 Nicholas C. Zakas
*/

/**
* Merges to arrays in order based on their natural
* relationship.
*
* @param {Array} left The first array to merge.
* @param {Array} right The second array to merge.
* @return {Array} The merged array.
*/
function merge(left, right){
var result = [];

while (left.length > 0 && right.length > 0){
if (left[0] < right[0]){
result.push(left.shift());
} else {
result.push(right.shift());
}
}

result = result.concat(left).concat(right);

//make sure remaining arrays are empty
left.splice(0, left.length);
right.splice(0, right.length);

return result;
}

/**
* Sorts an array in ascending natural order using
* merge sort.
*
* @param {Array} items The array to sort.
* @return {Array} The sorted array.
*/
function mergeSort(items){

// Terminal condition - don't need to do anything for arrays with 0 or 1 items
if (items.length < 2) {
return items;
}

var work = [],
i,
len;

for (i=0, len=items.length; i < len; i++){
work.push([items[i]]);
}
work.push([]);  //in case of odd number of items

for (var lim=len; lim > 1; lim = Math.floor((lim+1)/2)){
for (var j=0,k=0; k < lim; j++, k+=2){
work[j] = merge(work[k], work[k+1]);
}
work[j] = [];  //in case of odd number of items
}

return work[0];
}

/*
* Recursive merge sort implementation in JavaScript
* Copyright (c) 2012 Nicholas C. Zakas
*/

/**
* Merges to arrays in order based on their natural
* relationship.
*
* @param {Array} left The first array to merge.
* @param {Array} right The second array to merge.
* @return {Array} The merged array.
*/
function recursiveMerge(left, right){
var result  = [],
il      = 0,
ir      = 0;

while (il < left.length && ir < right.length){
if (left[il] < right[ir]){
result.push(left[il++]);
} else {
result.push(right[ir++]);
}
}

return result.concat(left.slice(il)).concat(right.slice(ir));
}

/**
* Sorts an array in ascending natural order using
* merge sort.
*
* @param {Array} items The array to sort.
* @return {Array} The sorted array.
*/
function recursiveMergeSort(items){

if (items.length < 2) {
return items;
}

var middle = Math.floor(items.length / 2),
left    = items.slice(0, middle),
right   = items.slice(middle),
params = recursiveMerge(recursiveMergeSort(left), recursiveMergeSort(right));

// Add the arguments to replace everything between 0 and last item in the array
params.unshift(0, items.length);
items.splice.apply(items, params);
return items;
}

/*
-----------------------------------------------------------------------------
Computer science in JavaScript: Bubble sort
-----------------------------------------------------------------------------

article: http://www.nczonline.net/blog/2009/05/26/computer-science-in-javascript-bubble-sort/
code: https://github.com/nzakas/computer-science-in-javascript/
*/

// bubble-sort.js

/**
* Swaps two values in an array.
*
* @param {Array} items The array containing the items.
* @param {int} firstIndex Index of first item to swap.
* @param {int} secondIndex Index of second item to swap.
* @return {void}
*/
function bubbleSortSwap(items, firstIndex, secondIndex){
var temp = items[firstIndex];
items[firstIndex] = items[secondIndex];
items[secondIndex] = temp;
}

/**
* A bubble sort implementation in JavaScript. The array
* is sorted in-place.
*
* @param {Array} items An array of items to sort.
* @return {Array} The sorted array.
*/
function bubbleSort(items){

var len = items.length,
i, j, stop;

for (i=0; i < len; i++){
for (j=0, stop=len-i; j < stop; j++){
if (items[j] > items[j+1]){
bubbleSortSwap(items, j, j+1);
}
}
}

return items;
}

// bubble-sort-2.js
//
// An alternative form of bubble sort can be accomplished by going through
// the array in the reverse order, so the items at the front of the array
// are placed in order first. To do so, simply reverse the loops.

/**
* Swaps two values in an array.
*
* @param {Array} items The array containing the items.
* @param {int} firstIndex Index of first item to swap.
* @param {int} secondIndex Index of second item to swap.
* @return {void}
*/
function bubbleSort2Swap(items, firstIndex, secondIndex){
var temp = items[firstIndex];
items[firstIndex] = items[secondIndex];
items[secondIndex] = temp;
}

/**
* A bubble sort implementation in JavaScript. The array
* is sorted in-place. This uses two reversed loops that
* count down instead of counting up.
*
* @param {Array} items An array of items to sort.
* @return {Array} The sorted array.
*/
function bubbleSort2(items){
var len = items.length,
i, j;

for (i=len-1; i >= 0; i--){
for (j=len-i; j >= 0; j--){
if (items[j] < items[j-1]){
bubbleSort2Swap(items, j, j-1);
}
}
}

return items;
}

//
// List Sorting Perfomance
//
// Jon LaBelle, <jon@jonlabelle.com>
//

// CONFIG

// How many unsorted list iterations will be performed
var unsortedListIterations = 100000;

// How many items will be generated for each unsorted list.
var unsortedListLength = 100;

// Unsorted list value range
//  ex: for list values between 1-100, set to `101`/
var unsortedListRange = 101;

// get a random list of numbers

function getUnsortedList() {
var list = new Array();

for (var i = 0; i < unsortedListLength; i++) {
list.push(Math.floor(Math.random() * unsortedListRange));
}

return list;
}

// START

console.time('selectionSort timer');
for (i = 0; i < unsortedListIterations; ++i) {
selectionSort(getUnsortedList());
}
console.timeEnd('selectionSort timer');

//

console.time('quickSort timer');
for (i = 0; i < unsortedListIterations; ++i) {
quickSort(getUnsortedList());
}
console.timeEnd('quickSort timer');

//

console.time('insertionSort timer');
for (i = 0; i < unsortedListIterations; ++i) {
insertionSort(getUnsortedList())
}
console.timeEnd('insertionSort timer');

//

console.time('mergeSort timer');
for (i = 0; i < unsortedListIterations; ++i) {
mergeSort(getUnsortedList());
}
console.timeEnd('mergeSort timer');

//

console.time('recursiveMergeSort timer');
for (i = 0; i < unsortedListIterations; ++i) {
recursiveMergeSort(getUnsortedList());
}
console.timeEnd('recursiveMergeSort timer');

//

console.time('bubbleSort timer');
for (i = 0; i < unsortedListIterations; ++i) {
bubbleSort(getUnsortedList());
}
console.timeEnd('bubbleSort timer');

//

console.time('bubbleSort2 timer');
for (i = 0; i < unsortedListIterations; ++i) {
bubbleSort2(getUnsortedList());
}
console.timeEnd('bubbleSort2 timer');``````