lib/heapsort.js
function dary(arity) {

	/**
  * Note that here we reverse the order of the
  * comparison operator since when we extract
  * values from the heap they can only be stored
  * at the end of the array. We thus build a max-heap
  * and then pop elements from it until it is empty.
  */

	var sort = function sort(compare, a, i, j) {

		// construct the max-heap

		var k = i + 1;

		for (; k < j; ++k) {

			var current = k - i;

			// while we are not the root

			while (current !== 0) {

				// address of the parent in a zero-based
				// d-ary heap

				var parent = i + ((current - 1) / arity | 0);
				current += i;

				// if current value is smaller than its parent
				// then we are done

				if (compare(a[current], a[parent]) <= 0) {
					break;
				}

				// otherwise
				// swap with parent

				var tmp = a[current];
				a[current] = a[parent];
				a[parent] = tmp;

				current = parent - i;
			}
		}

		// exhaust the max-heap

		for (--k; k > i; --k) {

			// put max element at the end of the array
			// and percolate new max element down
			// the heap

			var _tmp = a[k];
			a[k] = a[i];
			a[i] = _tmp;

			var _current = 0;

			while (true) {

				// address of the first child in a zero-based
				// d-ary heap

				var candidate = i + arity * _current + 1;

				// if current node has no children
				// then we are done

				if (candidate >= k) {
					break;
				}

				// search for greatest child

				var t = Math.min(candidate + arity, k);

				var y = candidate;

				for (++y; y < t; ++y) {

					if (compare(a[y], a[candidate]) > 0) {
						candidate = y;
					}
				}

				// if current value is greater than its greatest
				// child then we are done

				_current += i;

				if (compare(a[_current], a[candidate]) >= 0) {
					break;
				}

				// otherwise
				// swap with greatest child

				var _tmp2 = a[_current];
				a[_current] = a[candidate];
				a[candidate] = _tmp2;

				_current = candidate - i;
			}
		}
	};

	return sort;
}
function dary(arity) {

	/**
  * Note that here we reverse the order of the
  * comparison operator since when we extract
  * values from the heap they can only be stored
  * at the end of the array. We thus build a max-heap
  * and then pop elements from it until it is empty.
  */

	var sort = function sort(compare, a, i, j) {

		// construct the max-heap

		var k = i + 1;

		for (; k < j; ++k) {

			var current = k - i;

			// while we are not the root

			while (current !== 0) {

				// address of the parent in a zero-based
				// d-ary heap

				var parent = i + ((current - 1) / arity | 0);
				current += i;

				// if current value is smaller than its parent
				// then we are done

				if (compare(a[current], a[parent]) <= 0) {
					break;
				}

				// otherwise
				// swap with parent

				var tmp = a[current];
				a[current] = a[parent];
				a[parent] = tmp;

				current = parent - i;
			}
		}

		// exhaust the max-heap

		for (--k; k > i; --k) {

			// put max element at the end of the array
			// and percolate new max element down
			// the heap

			var _tmp = a[k];
			a[k] = a[i];
			a[i] = _tmp;

			var _current = 0;

			while (true) {

				// address of the first child in a zero-based
				// d-ary heap

				var candidate = i + arity * _current + 1;

				// if current node has no children
				// then we are done

				if (candidate >= k) {
					break;
				}

				// search for greatest child

				var t = Math.min(candidate + arity, k);

				var y = candidate;

				for (++y; y < t; ++y) {

					if (compare(a[y], a[candidate]) > 0) {
						candidate = y;
					}
				}

				// if current value is greater than its greatest
				// child then we are done

				_current += i;

				if (compare(a[_current], a[candidate]) >= 0) {
					break;
				}

				// otherwise
				// swap with greatest child

				var _tmp2 = a[_current];
				a[_current] = a[candidate];
				a[candidate] = _tmp2;

				_current = candidate - i;
			}
		}
	};

	return sort;
}
function dary ( arity ) { /**
  * Note that here we reverse the order of the
  * comparison operator since when we extract
  * values from the heap they can only be stored
  * at the end of the array. We thus build a max-heap
  * and then pop elements from it until it is empty.
  */ var sort = function sort ( compare , a , i , j ) { // construct the max-heap var k = i + 1 ; for ( ; k < j ; ++ k ) { var current = k - i ; // while we are not the root while ( current !== 0 ) { // address of the parent in a zero-based // d-ary heap var parent = i + ( ( current - 1 ) / arity | 0 ) ; current += i ; // if current value is smaller than its parent // then we are done if ( compare ( a [ current ] , a [ parent ] ) <= 0 ) { break ; } // otherwise // swap with parent var tmp = a [ current ] ; a [ current ] = a [ parent ] ; a [ parent ] = tmp ; current = parent - i ; } } // exhaust the max-heap for ( -- k ; k > i ; -- k ) { // put max element at the end of the array // and percolate new max element down // the heap var _tmp = a [ k ] ; a [ k ] = a [ i ] ; a [ i ] = _tmp ; var _current = 0 ; while ( true ) { // address of the first child in a zero-based // d-ary heap var candidate = i + arity * _current + 1 ; // if current node has no children // then we are done if ( candidate >= k ) { break ; } // search for greatest child var t = Math . min ( candidate + arity , k ) ; var y = candidate ; for ( ++ y ; y < t ; ++ y ) { if ( compare ( a [ y ] , a [ candidate ] ) > 0 ) { candidate = y ; } } // if current value is greater than its greatest // child then we are done _current += i ; if ( compare ( a [ _current ] , a [ candidate ] ) >= 0 ) { break ; } // otherwise // swap with greatest child var _tmp2 = a [ _current ] ; a [ _current ] = a [ candidate ] ; a [ candidate ] = _tmp2 ; _current = candidate - i ; } } } ; return sort ; }
Template for a d-ary implementation of heapsort.
Template for a d - ary implementation of heapsort .