/*
	Sorting.js - A compilation of sorting routines from around the interwebs
	2020 by mercury0x0d, Creative Commons Attribution 4.0 International License

	Revision history:
	2020-04-26 - Fixed missing declaration for variable 'index' in BinarySort(), added licensing
	2020-03-11 - Initial release
*/





var gHeapSortArrayLength;



function BinarySort(array)
{
	var arrayLength = array.length;
	var outputArray = [];
	var index, place;

	for (index = 0; index < arrayLength; index++)
	{
		place = _BinaryArraySearch(outputArray, array[index]);
		if (place >= 0) {outputArray.splice(place, 0, array[index]);}
	}

	return outputArray;
}



function BubbleSort(array)
{
	var index, swapped;
	do
	{
		swapped = false;
		for(index = 0; index < array.length; index++)
		{
			if(array[index] && array[index + 1] && array[index] > array[index + 1])
			{
				_SwapArrayElements(array, index, index + 1);
				swapped = true;
			}
		}
	} while(swapped);
}



function HeapSort(input)
{
	gHeapSortArrayLength = input.length;

	for (var i = Math.floor(gHeapSortArrayLength / 2); i >= 0; i -= 1)
	{
		_HeapRoot(input, i);
	}

	for (i = input.length - 1; i > 0; i--)
	{
		_SwapArrayElements(input, 0, i);
		gHeapSortArrayLength--;
		_HeapRoot(input, 0);
	}
}



function InsertionSort(array)
{
	var index, temp, testElement;


	for (var index = 0; index < array.length; index++)
	{
		temp = array[index];
		var testElement = index - 1;
		while (testElement >= 0 && array[testElement] > temp)
		{
			array[testElement + 1] = array[testElement];
			testElement--;
		}
		array[testElement + 1] = temp;
	}
}



function MergeSortBottomUp(array)
{
	var step = 1;
	while (step < array.length)
	{
		var left = 0;
		while (left + step < array.length)
		{
			_MergeBottomUp(array, left, step);
			left += step * 2;
		}
		step *= 2;
	}
	return array;
}



function MergeSortTopDown(array)
{
	if(array.length < 2)
	{
		return array;
	}

	var middle = Math.floor(array.length / 2);
	var left = array.slice(0, middle);
	var right = array.slice(middle);

	return _MergeTopDown(MergeSortTopDown(left), MergeSortTopDown(right));
}



function QuickSort(array)
{
	// basic implementation (pivot is the first element of the array)
	if (array.length < 2)
	{
		return array;
	}

	var pivot = array[0];
	var lesser = [];
	var greater = [];

	for (var i = 1; i < array.length; i++)
	{
		if(array[i] < pivot)
		{
			lesser.push(array[i]);
		} else {
			greater.push(array[i]);
		}
	}

	return QuickSort(lesser).concat(pivot, QuickSort(greater));
}



function QuickSortHoare(array, left, right)
{
	left = left || 0;
	right = right || array.length - 1;

	var pivot = _QuickSortPartitionHoare(array, left, right);

	if (left < pivot - 1)
	{
		QuickSortHoare(array, left, pivot - 1);
	}

	if (right > pivot)
	{
		QuickSortHoare(array, pivot, right);
	}

	return array;
}



function QuickSortLomuto(array, left, right)
{
	left = left || 0;
	right = right || array.length - 1;

	var pivot = _QuickSortPartitionLomuto(array, left, right);

	if (left < pivot - 1)
	{
		QuickSortLomuto(array, left, pivot - 1);
	}

	if (right > pivot)
	{
		QuickSortLomuto(array, pivot, right);
	}

	return array;
}



function RadixSortBucket (array)
{
	var indexA, indexB, indexC, len1, len2, radix, radixKey;
	var radices = {}, buckets = {}, num, curr;
	var currLen, radixStr, currBucket;

	len1 = array.length;

	// we're using ten buckets here
	len2 = 10;

	// find the relevant radices to process for efficiency
	for (indexA = 0;indexA < len1;indexA++)
	{
		radices[array[indexA].toString().length] = 0;
	}

	// loop for each radix. For each radix we put all the items
	// in buckets, and then pull them out of the buckets.
	for (radix in radices)
	{
		// put each array item in a bucket based on its radix value
		len1 = array.length;
		for (indexA = 0; indexA < len1; indexA++)
		{
			curr = array[indexA];

			// item length is used to find its current radix value
			currLen = curr.toString().length;

			// only put the item in a radix bucket if the item
			// key is as long as the radix
			if (currLen >= radix)
			{
				// radix starts from beginning of key, so need to
				// adjust to get redix values from start of stringified key
				radixKey = curr.toString()[currLen - radix];

				// create the bucket if it does not already exist
				if (!buckets.hasOwnProperty(radixKey))
				{
					buckets[radixKey] = [];
				}

				// put the array value in the bucket
				buckets[radixKey].push(curr);
			} else {
				if (!buckets.hasOwnProperty('0'))
				{
					buckets['0'] = [];
				}
				buckets['0'].push(curr);
			}
		}

		// for current radix, items are in buckets, now put them
		// back in the array based on their buckets
		// this index moves us through the array as we insert items
		indexA = 0;

		// go through all the buckets
		for (indexB = 0; indexB < len2; indexB++)
		{
			// only process buckets with items
			if (buckets[indexB] != null)
			{
				currBucket = buckets[indexB];

				// insert all bucket items into array
				len1 = currBucket.length;
				for (indexC = 0; indexC < len1; indexC++)
				{
					array[indexA++] = currBucket[indexC];
				}
			}
		}
		buckets = {};
	}
}



function RadixSortLSD(array)
{
	var counter = [ [] ];
	var max = 0,
	mod = 10,
	dev = 1; //max
	for (var i = 0; i < array.length; i++)
	{
		if (array[i] > max)
		{
			max = array[i];
		}
	}

	// determine the large item length
	var maxDigitLength = (max + '').length;
	for (var i = 0; i < maxDigitLength; i++, dev *= 10, mod *= 10)
	{
		for (var j = 0; j < array.length; j++)
		{
			var bucket = Math.floor((array[j] % mod) / dev); // Formula to get the significant digit
			if (counter[bucket] == undefined) {
			counter[bucket] = [];
			}	
			counter[bucket].push(array[j]);
		}

		var pos = 0;
		for (var j = 0; j < counter.length; j++)
		{
			var value = undefined;
			if (counter[j] != undefined)
			{
				while ((value = counter[j].shift()) != undefined)
				{
					array[pos++] = value;
				}
			}
		}
	}
};



function SelectionSort(array)
{
	var index, minimum, testElement;


	for (var index = 0; index < array.length; index++)
	{
		minimum = index;
		for (var testElement = index + 1; testElement < array.length; testElement++)
		{
			if (array[testElement] < array[minimum]) 
			{
				minimum = testElement;
			}
		}
		if (index !== minimum)
		{
			_SwapArrayElements(array, index, minimum);
		}
	}
	return array;
}



function ShellSort(array)
{
	var gaps = [701, 301, 132, 57, 23, 10, 4, 1];


	for (var g = 0; g < gaps.length; g++)
	{
		var gap = gaps[g];
		for (var i = gap; i < array.length; i++)
		{
			var temp = array[i];
			for (var j = i; j >= gap && array[j - gap] > temp; j -= gap)
			{
				array[j] = array[j - gap];
			}
			array[j] = temp;
		}
	}
}



function _BinaryArraySearch(inputArray, searchValue)
{
	var lowerBound = 0, middle;
	var upperBound = inputArray.length - 1;

	while (lowerBound <= upperBound)
	{
		middle = Math.floor(lowerBound + ((upperBound - lowerBound) / 2));

		if (inputArray[middle] == searchValue)
		{
			// the item was found!
			return middle;
		} else if (searchValue < inputArray[middle])
		{
			upperBound = middle - 1;
		} else {
			lowerBound = middle + 1;
		}
	}
	return lowerBound
}



function _HeapRoot(input, i)
{
	var left = 2 * i + 1;
	var right = 2 * i + 2;
	var max = i;

	if (left < gHeapSortArrayLength && input[left] > input[max])
	{
		max = left;
	}

	if (right < gHeapSortArrayLength && input[right] > input[max])
	{
		max = right;
	}

	if (max != i)
	{
		_SwapArrayElements(input, i, max);
		_HeapRoot(input, max);
	}
}



function _MergeBottomUp(array, left, step)
{
	var right = left + step;
	var end = Math.min(left + step * 2 - 1, array.length - 1);
	var leftMoving = left;
	var rightMoving = right;
	var temp = [];

	for (var i = left; i <= end; i++)
	{
		if ((array[leftMoving] <= array[rightMoving] || rightMoving > end) && leftMoving < right)
		{
			temp[i] = array[leftMoving];
			leftMoving++;
		} else {
			temp[i] = array[rightMoving];
			rightMoving++;
		}
	}

	for (var j = left; j <= end; j++)
	{
		array[j] = temp[j];
	}
}



function _MergeTopDown(left, right)
{
	var array = [];

	while(left.length && right.length)
	{
		if(left[0] < right[0])
		{
			array.push(left.shift());
		} else {
			array.push(right.shift());
		}
	}
	return array.concat(left.slice()).concat(right.slice());
}



function _QuickSortPartitionHoare(array, left, right)
{
	// Hoare partitioning is more efficient than Lomuto; on average it does three times fewer swaps
	var pivot = Math.floor((left + right) / 2 );

	while (left <= right)
	{
		while (array[left] < array[pivot])
		{
			left++;
		}

		while (array[right] > array[pivot])
		{
			right--;
		}

		if (left <= right)
		{
			_SwapArrayElements(array, left, right);
			left++;
			right--;
		}
	}
	return left;
}



function _QuickSortPartitionLomuto(array, left, right)
{
	// Lomuto partitioning is less efficient than Hoare
	var pivot = right;
	var i = left;

	for (var j = left; j < right; j++)
	{
		if (array[j] <= array[pivot])
		{
			_SwapArrayElements(array, i , j);
			i = i + 1;
		}
	}
	_SwapArrayElements(array, i, j);
	return i;
}



function _SwapArrayElements(array, indexA, indexB)
{
	var temp;


	temp = array[indexA];
	array[indexA] = array[indexB];
	array[indexB] = temp;
}