# Sorting Algorithms (v36)

## Description

Sort 1000 numbers

## Preparation HTML

``````<script>
function swap(ary, a, b) {
var t = ary[a];
ary[a] = ary[b];
ary[b] = t;
}

// Built-in with comparison function (default sorting is "dictionary-style")
function builtin_sort(ary) {
return ary.sort(function(a, b) {
return a - b;
});
}

// Bubble Sort
function bubble_sort(ary) {
var a, b;
for (a = 0; a < ary.length; a++) {
for (b = a + 1; b < ary.length; b++) {
if (ary[a] > ary[b]) {
swap(ary, a, b);
}
}
}

return ary;
}
//Insertion sort
function insertion_sort(ary) {
for(var i=1,l=ary.length;i<l;i++) {
var value = ary[i];
for(var j=i - 1;j>=0;j--) {
if(ary[j] <= value)
break;
ary[j+1] = ary[j];
}
ary[j+1] = value;
}
return ary;
}

// Naive (but understandable) quicksort (memory hog)
function naive_quicksort(ary) {
if (ary.length <= 1) {
return ary;
}

var less = [],
greater = [],
pivot = ary.pop();

for (var i = 0; i < ary.length; i++) {
if (ary[i] < pivot) {
less.push(ary[i]);
} else {
greater.push(ary[i]);
}
}

less = naive_quicksort(less);
greater = naive_quicksort(greater);

return less.concat(pivot, greater);
}

// In place quicksort
function inplace_quicksort_partition(ary, start, end, pivotIndex) {
var i = start, j = end;
var pivot = ary[pivotIndex];

while(true) {
while(ary[i] < pivot) {i++};
j--;
while(pivot < ary[j]) {j--};
if(!(i<j)) {
return i;
}
swap(ary,i,j);
i++;
}
}

function inplace_quicksort(ary, start, end) {
if (start < end - 1) {
var pivotIndex = Math.round((start + end) / 2);

pivotIndex = inplace_quicksort_partition(ary, start, end, pivotIndex);

inplace_quicksort(ary, start, pivotIndex - 1);
inplace_quicksort(ary, pivotIndex + 1, end);
}

return ary;
}

// Heap sort
function heapSort(ary) {
heapify(ary);

for (var end = ary.length - 1; end > 0; end--) {
swap(ary, end, 0);
shiftDown(ary, 0, end - 1);
}

return ary;
}

function heapify(ary) {
for (var start = (ary.length >> 1) - 1; start >= 0; start--) {
shiftDown(ary, start, ary.length - 1);
}
}

function shiftDown(ary, start, end) {
var root = start,
child, s;

while (root * 2 + 1 <= end) {
child = root * 2 + 1;
s = root;

if (ary[s] < ary[child]) {
s = child;
}

if (child + 1 <= end && ary[s] < ary[child + 1]) {
s = child + 1;
}

if (s !== root) {
swap(ary, root, s);
root = s;
} else {
return;
}
}
}

// Merge sort
function merge_sort(ary) {
if (ary.length <= 1) {
return ary;
}

var m = ary.length >> 1;

var left = ary.slice(0, m),
right = ary.slice(m);

return merge(merge_sort(left), merge_sort(right));
}

function merge(left, right) {
var result = [],
li = 0, ri = 0;

while (li < left.length || ri < right.length) {
if (li < left.length && ri < right.length) {
if (left[li] <= right[ri]) {
result.push(left[li]);
li++;
} else {
result.push(right[ri]);
ri++;
}
} else if (li < left.length) {
result.push(left[li]);
li++;
} else if (ri < right.length) {
result.push(right[ri]);
ri++;
}
}

return result;
}

// Shell sort
function shell_sort(ary) {
var inc = Math.round(ary.length / 2),
i, j, t;

while (inc > 0) {
for (i = inc; i < ary.length; i++) {
t = ary[i];
j = i;
while (j >= inc && ary[j - inc] > t) {
ary[j] = ary[j - inc];
j -= inc;
}
ary[j] = t;
}
inc = Math.round(inc / 2.2);
}

return ary;
}
//Comb Sort (Basically bubblesort with a small modification, but heaps faster)
function comb_sort(ary) {
var gap = ary.length;
while(true) {
gap = newgap(gap);
var swapped = false;
for(var i=0,l=ary.length;i<l;i++) {
var j = i + gap;
if(ary[i] < ary[j]) {
swap(ary,i,j);
swapped = true;
}
}
if(gap == 1 && !swapped)
break;
}
return ary;
}
function newgap(gap) {
gap = ((gap * 10) / 13) | 0;
if(gap == 9 || gap == 10)
gap = 11;
if(gap < 1)
gap = 1;
return gap;
}
//faster quicksort using a stack to eliminate recursion, sorting inplace to reduce memory usage, and using insertion sort for small partition sizes
//It should NOT be running at the EXACT same speed as the inplace version due to the number of changes, but it does on jsPerf for some reason....
function fast_quicksort(ary) {
var stack = [];
var entry = [0,ary.length,2 * Math.floor(Math.log(ary.length)/Math.log(2))];
stack.push(entry);
while(stack.length > 0) {
entry = stack.pop();
var start = entry[0];
var end = entry[1];
var depth = entry[2];
if(depth == 0) {
ary = shell_sort_bound(ary,start,end);
continue;
}
depth--;
var pivot = Math.round((start + end) / 2);

var pivotNewIndex = inplace_quicksort_partition(ary,start,end, pivot);
if(end - pivotNewIndex > 16) {
entry = [pivotNewIndex,end,depth];
stack.push(entry);
}
if(pivotNewIndex - start > 16) {
entry = [start,pivotNewIndex,depth];
stack.push(entry);
}
}
ary = insertion_sort(ary);
return ary;
}
function shell_sort_bound(ary,start,end) {
var inc = Math.round((start + end)/2),
i, j, t;

while (inc >= start) {
for (i = inc; i < end; i++) {
t = ary[i];
j = i;
while (j >= inc && ary[j - inc] > t) {
ary[j] = ary[j - inc];
j -= inc;
}
ary[j] = t;
}
inc = Math.round(inc / 2.2);
}

return ary;
}

function mysort(arr) {
var len = arr.length;
var lp = -1;

for (var i=0; i<len-1; ) {
var p1 = arr[i], p2 = arr[i+1];
if (p1 > p2) {
arr[i] = p2; arr[i+1] = p1; lp = i; i -= 1;
if (i < 0) {
i = 0;
}
}
else if (lp == -1) { i++; }
else { i = lp + 1; lp++ }
}
return arr;
}

// golden sort (https://gist.github.com/javiercejudo/d8f57d44af4fef68b9d5)
function getOptimalStrategyFast(n) {
return Math.round(n / Math.E);
}

function goldenSort(arrayToSort) {
var currentStrategy,
relevantArrayLenght = arrayToSort.length,
relevantArrayLastIndex = relevantArrayLenght - 1,
currentMax,
currentMaxIndex,
index,
done;

do {
currentMax = -Infinity;
index = 0;
currentStrategy = getOptimalStrategyFast(relevantArrayLenght);

do {
if (currentMax < arrayToSort[index]) {
currentMax = arrayToSort[index];
currentMaxIndex = index;
}

index += 1;
} while (index < currentStrategy);

done = false;

do {
if (currentMax < arrayToSort[index]) {
if (index !== relevantArrayLastIndex && arrayToSort[relevantArrayLastIndex] < arrayToSort[index]) {
done = true;
swap(arrayToSort, relevantArrayLastIndex, index);
}
}

index += 1;
} while (index < relevantArrayLenght && done === false);

if (done === false) {
if (arrayToSort[relevantArrayLastIndex] < arrayToSort[currentMaxIndex]) {
swap(arrayToSort, currentMaxIndex, relevantArrayLastIndex);
}

relevantArrayLenght -= 1;
relevantArrayLastIndex -= 1;
}
} while (relevantArrayLenght > 1);

return arrayToSort;
}
</script>``````

## Setup

``````var input = [];
for (var i = 0; i < 5000; i++) {
input[i] = Math.round(Math.random() * 60000);
}``````

## Teardown

``````
for (var i = 0; i < 5000; i++) {
if (ret[i] > ret[i] + 1) {
throw Error('Array is not sorted');
}
}
``````

## Test runner

Ready to run.

Testing in
TestOps/sec
Built-in Sort
``ret = builtin_sort(input.slice(0));``
ready
Bubble Sort
``ret = bubble_sort(input.slice(0));``
ready
Naive Quicksort
``ret = naive_quicksort(input.slice(0));``
ready
Inplace Quicksort
``ret = inplace_quicksort(input.slice(0), 0, 5000);``
ready
Heap Sort
``ret = heapSort(input.slice(0));``
ready
Merge Sort
``ret = merge_sort(input.slice(0));``
ready
Shell Sort
``ret = shell_sort(input.slice(0));``
ready
Comb Sort
``ret = comb_sort(input.slice(0));``
ready
Insertion Sort
``ret = insertion_sort(input.slice(0));``
ready
Fast QuickSort
``ret = fast_quicksort(input.slice(0));``
ready
MySort
``ret = mysort(input.slice(0));``
ready
Golden Sort
``ret = goldenSort(input.slice(0));``
ready

## Revisions

You can edit these tests or add more tests to this page by appending /edit to the URL.