# Analysis of JavaScript Sort Algorithms

The other day I wrote an article about JavaScript binary trees and mentioned that the native JavaScript sort was probably faster than using a binary tree for sorting. I decided to write a few sort algorithms in JavaScript and see how they compared to the native ".sort()".

I tested each sort method with three types of data sets. The first data set was made up of all the same number, the second set was an ascending series of numbers, and the third set was made up of random numbers between zero and four hundred. I used different data set sizes, from 25 to 4000. Finally, I ran the test 22 times, discarded the highest and lowest results, and averaged the remaining results.
As you may have guessed, the native JavaScript sort method handily beat all of the methods that I implemented. There really were no surprises, but it gave me the opportunity to implement various sort algorithms. It is hard to make it out in the picture above, but the built-in sort function is displayed on the graph as a nearly vertical white line. The black line above it is quicksort. This graph show the performance of these algorithms on the random data set.

My empirical analysis also showed that the red-headed-stepchild of algorithms, bubble sort, could actually beat the king, quicksort, under carefully constructed conditions. The graph below shows the results when sorting attempting to sort an array that is already sorted. The furthest left black line shows the terrible performance of quicksort under these conditions. Bubble sort performed well, it was only beat by its big brother cocktail sort and sort() which again beat all of my implementations.
The moral of the story is that you don't want to use quick sort on arrays that are already nearly sorted. Furthermore, the built-in JavaScript ".sort()" can beat all of my implementations using any of my data sets for nearly every data set size.

For the curious my code is listed below:

<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Strict//EN"
"http://www.w3.org/TR/xhtml1/DTD/xhtml1-strict.dtd">
<title>Sort Tester</title>
<meta http-equiv="Content-Type"
content="application/xhtml+xml; charset=iso-8859-1" />
<meta name="generator"
content="Christopher Stoll - using a text editor" />
type="image/vnd.microsoft.icon"
href="img/favicon.ico" />
type="image/vnd.microsoft.icon"
href="img/favicon.ico" />
type="text/css"
href="css/main.css" />
<script type="text/javascript"
src="js/jquery-1.4.2.min.js"></script>
<script type="text/javascript"
src="js/Array.extrasort.js"></script>
<script type="text/javascript">
/**
* sortTest object constructor
*
* @constructor
* @this {sortTest}
*/
function sortTest(){
// array to be sorted
this._array = [];
// array of sort times (length is _num_times)
this._times = [];
// number of times to sort the array
this._numTests = 12;

// the array modes
this.modes = {random:0, same:1, ascending:2};
// the sort types
this.sorts = {
default:  {id:0, name:'sort()'},
bubble:    {id:1, name:'bubble'},
cocktail:  {id:2, name:'cocktail'},
heap:    {id:3, name:'heap'},
insertion:  {id:4, name:'insertion'},
merge:    {id:5, name:'merge'},
quick:    {id:6, name:'quick'},
selection:  {id:8, name:'selection'},
tree:    {id:9, name:'tree'}
}

// array of array sizes to test
this.arraySizes =
[25, 50, 75, 100, 200, 400, 600, 800, 1000
1200, 1400, 1600, 2000, 2200, 2400, 2600, 2800
3200, 3400, 3600, 3800, 4000];
// 400 random nums from 000-400
// (the random number generator wasn't working well)
this._array400 =
[191, 137, 335, 070, 382, 399, 287, 107, 016, 302
310, 324, 363, 113, 019, 198, 305, 238, 390, 366,
199, 201, 503, 161, 012, 266, 281, 325, 314, 213,
335, 197, 284, 362, 395, 068, 359, 143, 233, 356,
025, 144, 308, 352, 280, 029, 328, 313, 284, 064,
074, 128, 202, 392, 001, 351, 200, 392, 261, 230,
073, 218, 022, 133, 376, 030, 082, 253, 134, 146,
065, 171, 299, 251, 255, 269, 105, 274, 302, 185,
321, 345, 057, 280, 244, 074, 081, 165, 126, 098,
140, 277, 255, 000, 004, 072, 132, 170, 165, 281,
026, 132, 200, 184, 338, 297, 348, 231, 356, 337,
114, 219, 070, 185, 041, 090, 193, 012, 010, 243,
144, 013, 236, 238, 140, 054, 105, 094, 292, 021,
124, 332, 123, 019, 129, 138, 368, 303, 391, 090,
002, 270, 232, 274, 382, 067, 386, 371, 009, 183,
239, 218, 086, 097, 037, 239, 388, 030, 360, 174,
146, 267, 260, 152, 133, 209, 168, 320, 234, 055,
130, 374, 396, 049, 346, 034, 277, 093, 360, 163,
253, 051, 216, 259, 384, 110, 355, 208, 206, 383,
158, 163, 296, 304, 196, 098, 115, 123, 122, 073,
239, 218, 086, 097, 037, 239, 388, 030, 360, 174,
146, 267, 260, 152, 133, 209, 168, 320, 234, 055,
130, 374, 396, 049, 346, 034, 277, 093, 360, 163,
253, 051, 216, 259, 384, 110, 355, 208, 206, 383,
158, 163, 296, 304, 196, 098, 115, 123, 122, 073,
010, 334, 293, 067, 354, 323, 314, 269, 292, 399,
175, 281, 156, 309, 132, 031, 161, 075, 363, 103,
262, 133, 322, 098, 305, 323, 386, 369, 198, 023,
166, 233, 266, 140, 038, 389, 342, 110, 291, 037,
328, 263, 147, 060, 255, 231, 096, 392, 197, 028,
199, 071, 187, 270, 268, 325, 366, 278, 017, 204,
289, 180, 242, 377, 133, 112, 388, 260, 166, 136,
163, 037, 373, 178, 074, 220, 304, 163, 206, 118,
028, 099, 281, 377, 202, 286, 214, 239, 209, 128,
229, 239, 141, 340, 309, 094, 298, 028, 299, 347,
027, 296, 041, 059, 112, 281, 188, 002, 037, 400,
118, 033, 338, 399, 367, 050, 302, 048, 097, 258,
297, 057, 055, 316, 159, 133, 268, 010, 245, 031,
215, 235, 009, 242, 113, 112, 268, 037, 182, 074,
104, 326, 180, 159, 375, 264, 229, 288, 312, 273,
340, 204, 057, 306, 073, 221, 173, 283, 279, 394];
}
/**
* fill array with values
*
* @private
* @this {sortTest}
* @param {numeric} pnum size of the array
* @param {boolean} pmod the mode
*/
sortTest.prototype._fillArray = function(pnum, pmod) {
var tmod = pmod || this.modes.random,
count0=0;

this._array = [];

// array with ascending numbers
if(tmod == this.modes.ascending){
for(var i=0; i<pnum; i++){
this._array[i] = i;
}
// array with same number
} else if(tmod == this.modes.same){
for(var i=0; i<pnum; i++){
this._array[i] = 123;
}
// array with random numbers
} else {
if(pnum <= 400){
for(var i=0; i<pnum; i++){
this._array[i] = this._array400[i];
}
} else {
for(var i=0; i<pnum; i++){
if(i>400){
count0 =
Math.floor(Math.random()*400);
this._array[i] =
this._array400[count0];
} else {
this._array[i] =
this._array400[i];
}
}
}
}
}

/**
* fill with random values that are nearly sorted
*
* @this {sortTest}
* @param {numeric} pnum size of the array
*/
sortTest.prototype.gen = function(pnum) {
this._fillArray(pnum);
}

/**
* fill array with ascending values
*
* @this {sortTest}
* @param {numeric} pnum size of the array
*/
sortTest.prototype.genAscending = function(pnum) {
this._fillArray(pnum, this.modes.ascending);
}

/**
* fill array same values
*
* @this {sortTest}
* @param {numeric} pnum size of the array
*/
sortTest.prototype.genSame = function(pnum) {
this._fillArray(pnum, this.modes.same);
}

/**
* get the average time from the times array
*
* @private
* @this {sortTest}
* @return {numeric} the average time
*/
sortTest.prototype._timeAvg = function(){
var time_sum = 0// sum of the times
time_min = 0// the minimum time
time_max = 0// the maximum time
time_avg = 0// the average time

// use the first item as the default minimum
time_min = this._times[0];

for(var i=0; i<this._numTests; i++){
time_sum += this._times[i];

// so we can discard highest and lowest
if(this._times[i] < time_min){
time_min = this._times[i];
} else if(this._times[i] > time_max){
time_max = this._times[i];
}
}
// average time is the sum minus the high
// and low divided by nuber minus two
time_avg =
(time_sum - time_min - time_max) /
(this._numTests - 2);
return time_avg.toFixed(2);
}

/**
* get a timestamp
*
* @private
* @this {sortTest}
* @return {numeric} time stamp
*/
sortTest.prototype._getTS = function() {
var datetime = new Date();
return datetime.getTime();
}

/**
* run the specified sort
*
* @this {sortTest}
* @param {numeric} ptype The type of sort
* @return {numeric} Changed succesfully
*/
sortTest.prototype.run = function(ptype){
var ttype = ptype || this.sorts.default,
time_beg = 0// the starting time
time_end = 0// the ending time
time_tot = 0// end time minus start time
tmp_array = [];  // array to sort

for(var i=0; i<this._numTests; i++){
// get a fresh COPY (use slice) of array
tmp_array = this._array.slice(0);

switch(ttype){
// this sorts as strings
case this.sorts.default:
time_beg = this._getTS();
tmp_array.sort();
time_end = this._getTS();
break;
case this.sorts.bubble:
time_beg = this._getTS();
tmp_array.bubbleSort();
time_end = this._getTS();
break;
case this.sorts.cocktail:
time_beg = this._getTS();
tmp_array.cocktailSort();
time_end = this._getTS();
break;
case this.sorts.selection:
time_beg = this._getTS();
tmp_array.selectionSort();
time_end = this._getTS();
break;
case this.sorts.insertion:
time_beg = this._getTS();
tmp_array.insertionSort();
time_end = this._getTS();
break;
case this.sorts.merge:
time_beg = this._getTS();
tmp_array = tmp_array.mergeSort();
time_end = this._getTS();
break;
case this.sorts.heap:
time_beg = this._getTS();
tmp_array = tmp_array.heapSort();
time_end = this._getTS();
break;
case this.sorts.quick:
time_beg = this._getTS();
tmp_array = tmp_array.quickSort();
time_end = this._getTS();
break;
//  time_beg = this._getTS();
//  time_end = this._getTS();
break;
case this.sorts.tree:
//  time_beg = this._getTS();
//  tmp_array.treeSort();
//  time_end = this._getTS();
break;
}

// total time, stored
time_tot = time_end - time_beg;
this._times[i] = time_tot;
}

this._array = [];
this._array = tmp_array;
return this._timeAvg();
}

/*
* ***** ***** ***** ***** *****
* Above is the tester program
* Below is the GUI portion
* ***** ***** ***** ***** *****
*/

sorter = new sortTest();
});

function runSort(pSortType) {
var result_same = 0,
result_ascending = 0,
result_random = 0,
result = '',
skip = false;

// run for each array size
for(var i=0; i<sorter.arraySizes.length; i++){
skip = false;

if(sorter.arraySizes[i]>1000 &&
pSortType == sorter.sorts.quick)
{skip = true;}
if(sorter.arraySizes[i]>2000 &&
pSortType == sorter.sorts.selection)
{skip = true;}

// run for a uniform array (if it is not too big)
if(!skip){
sorter.genSame(sorter.arraySizes[i]);
result_same = sorter.run(pSortType);
} else {
result_same = 999;
}

// run for a sorted array (if it is not too big)
if(!skip){
sorter.genAscending(sorter.arraySizes[i]);
result_ascending = sorter.run(pSortType);
} else {
result_ascending = 999;
}

if(pSortType == sorter.sorts.quick)
{skip = false;}
if(sorter.arraySizes[i]>1200 &&
pSortType == sorter.sorts.bubble)
{skip = true;}
if(sorter.arraySizes[i]>1400 &&
pSortType == sorter.sorts.cocktail)
{skip = true;}
if(sorter.arraySizes[i]>2000 &&
pSortType == sorter.sorts.insertion)
{skip = true;}

// run for a random(ish) array (if not too big)
if(!skip){
sorter.gen(sorter.arraySizes[i]);
result_random = sorter.run(pSortType);
} else {
result_random = 999;
}

result =  '<td>' + pSortType.name + '</td>';
result += '<td>' + sorter.arraySizes[i] + '</td>';
result += '<td>' + result_same + '</td>';
result += '<td>' + result_ascending + '</td>';
result += '<td>' + result_random + '</td>';
\$('#results').append('<tr>'+result+'</tr>');
}
}
</script>
<div id="app_data"></div>
<div id="colc">
<input type="button" value="Run deafult"
onclick="runSort(sorter.sorts.default);">
<input type="button" value="Run bubble"
onclick="runSort(sorter.sorts.bubble);">
<input type="button" value="Run cocktail"
onclick="runSort(sorter.sorts.cocktail);">
<input type="button" value="Run selection"
onclick="runSort(sorter.sorts.selection);">
<input type="button" value="Run insertion"
onclick="runSort(sorter.sorts.insertion);">
<input type="button" value="Run merge"
onclick="runSort(sorter.sorts.merge);">
<input type="button" value="Run heap"
onclick="runSort(sorter.sorts.heap);">
<input type="button" value="Run quick"
onclick="runSort(sorter.sorts.quick);">