// ====================================================================================================================
// Copyright (c) 2003,2004  Henk Reints, http://henk-reints.nl
// -----------------------------------------------------------
//
// Usage:	first read this as a text file in order to learn about sorting. (with line wrapping DISabled!)
//		then run it as follows to see it in action:
//		- open a Command Prompt in the directory where you saved this file
//		- type "cscript hr$arraysortdemo.wsf"
//		- press [Enter]
//
// About sorting
// -------------
// How can Array elements be sorted?
// Well, suppose we do the following (where A represents the Array containing the elements to be sorted):
//
//	// Step 1: find the smallest element in A (k will eventually point to the smallest element of A):
//
//		for (var k = 0, i = k + 1; i < A.length; i++) {if (A[i] < A[k]) k = i}
//
//	// Step 2: exchange the elements 0 and k:
//
//		var x = A[0]; A[0] = A[k]; A[k] = x
//
// Then A will now have its smallest element at its first position and the rest is random.
// This process could be repeated for the part of A behind this position,
// then we would get the second smallest element at the second position.
// And that could be repeated throughout the entire Array, giving the following sorting algorithm:
// --------------------------------------------------------------------------------------------------------------------

Array.prototype.simpleSort = function simpleSort ()
{
	for (var j = 0; j < this.length; j++)
	{	for (var k = j, i = j + 1; i < this.length; i++) {if (this[i] < this[k]) k = i}
		if (k != j) {var x = this[j]; this[j] = this[k]; this[k] = x}
	}
}

// --------------------------------------------------------------------------------------------------------------------
// This is a correct sorting algorithm, but it is not very efficient.
// The number of compares it does will be (assuming N is the number of elements in A):
//
//	for the first search:	N-1	(i.e. the first  time that the inner 'for' loop is executed)
//	then			N-2	(i.e. the second time that the inner 'for' loop is executed)
//	then			N-3
//	etc.			:
//	finally			3
//	then			2	(i.e. the second last time that the inner 'for' loop is executed)
//	then			1	(i.e. the very   last time that the inner 'for' loop is executed)
//
// All these counts must be added together, so 1 + 2 + 3 + ... + (N-3) + N-2) + (N-1)
// and the result is:
//			N * (N-1) / 2
//
// This is practically equal to square(N)/2  [square(N) means N*N, of course].
//
// Now suppose we have to sort 100 elements. That will take 100*99/2 = 4950 compares.
// Could we do something smarter? Yes!
//
// For sorting 50 elements we would need only 50*49/2 = 1225 compares.
// And for sorting 2 sets of 50 elements it would need 2*1225 = 2450 compares.
// Now let's simply split the original 100 elements into 2 sets of 50 elements each and sort them.
// Then we'll get 2 sorted sets of 50 elements, which has taken 2450 compares.
// But then these 2 sorted sets must still be merged into 1 single sorted set.
// And that appears to be easy AND efficient.
// Suppose the elements are numbers written on cards.
// Then we have 2 stacks of 50 numbered cards which HAVE ALREADY BEEN SORTED.
// Put those 2 stacks of cards on the table face up (assuming the sorting is such that the smallest
// number of each set is now on top).
// You'll see 2 numbers.
// Take the card with the smallest number and put that face down on a new stack.
// Then repeat this until one of the input stacks is empty.
// Put the remaining other stack face down on the new stack.
// Ready.
// You now have 1 set of cards, sorted by the numbers written on them.
// And how many compares have you done? At least 50 and at most 99. Let's assume the worst case, so 99.
// The total number of compares we have done to sort 100 elements is now: 2450 + 99 = 2549.
// That's just a little bit more than half of the 4950 compares needed to sort them with the first algorithm!
//
// So sorting a set can be done more efficiently by dividing the set into two halves, sorting those halves,
// and then merging them together. It will take just a bit more than half the time of the elementary sorting
// method.
//
// Now let's be really smart: why not do the very same for sorting those 2 halves?
// We'd gain another factor 2.
// For sorting 25 elements we need only 25*24/2 = 300 compares.
// Sorting 50 elements would then take 2*300+49 = 649 compares instead of 1225.
// 
// We'll now repeat this process until the set can no longer be divided in 2 halves.
// That's the smart way of sorting.
// The total number of compares will become practically equal to N * Log2(N) [where Log2 means the base-2 logarithm].
// For large values of N that's a VERY significant improvement!
//
// When programming in a modern language like JavaScript, we can implement this by RECURSIVE programming.
// That means a functions that can invoke itself.
// Look:
// --------------------------------------------------------------------------------------------------------------------

Array.prototype.getSortedCopyRecursive = function getSortedCopyRecursive()
{
	function merge (A1, A2)					// assumes that A1 and A2 are both already sorted in the correct order
	{	var A = new Array (A1.length + A2.length)				// new Array for result
		for (var i = 0, i1 = 0, i2 = 0; i1 < A1.length && i2 < A2.length; )	// loop until either A1 or A2 is done
		{	if (A1[i1] <= A2[i2])	A[i++] = A1[i1++]			// take the "left card" if that's the smallest
			else			A[i++] = A2[i2++]			// else take the "right card"
		}							// now either A1 or A2 is not yet done
		for (; i1 < A1.length; A[i++] = A1[i1++] );		// one of these 2 loops will actually
		for (; i2 < A2.length; A[i++] = A2[i2++] );		// copy the remainder of either A1 or A2 to A
		return A						// ready, return the result
	}
	function sort (A)
	{	if (A.length < 2) return A.slice(0)		// nothing to sort, leave with a copy of A
		var A1 = sort (A.slice (0, A.length/2) )	// sort the first half
		var A2 = sort (A.slice (A.length/2) )		// and the second half 
		return merge (A1, A2)				// and return them merged together
	}
	return sort (this)
}

// --------------------------------------------------------------------------------------------------------------------
// This method will return a sorted COPY of the Array.
// Isn't it nice?
//
// There's another way to increase the speed of sorting.
// As you can see, we are constantly copying or moving the actual Array elements to other places.
// If the elements themselves are large (e.g. long Strings or so) then that takes a lot of time.
// It's much better to build another Array which contains pointers to the elements that must be sorted,
// and then manipulate only those pointers:
// --------------------------------------------------------------------------------------------------------------------

Array.prototype.getSortedIndexRecursive = function getSortedIndexRecursive()
{
	var A = this
	function merge (X1, X2)
	{	var X = new Array (X1.length + X2.length)
		for (var i = 0, i1 = 0, i2 = 0; i1 < X1.length && i2 < X2.length; )
		{	if (A[X1[i1]] <= A[X2[i2]])	X[i++] = X1[i1++]
			else				X[i++] = X2[i2++]
		}
		for (; i1 < X1.length; X[i++] = X1[i1++] );
		for (; i2 < X2.length; X[i++] = X2[i2++] );
		return X
	}
	function sort (X)
	{	if (X.length < 2) return X
		var X1 = sort (X.slice (0, X.length/2) )	// get sorted index of the first half
		var X2 = sort (X.slice (X.length/2) )		// and of the second half
		return merge (X1, X2)				// and return them merged together
	}
	for (var i = 0, X = []; i < this.length; X[i] = i++);	// build an index
	return sort (X)						// and return it sorted
}

// --------------------------------------------------------------------------------------------------------------------
// There is however a price to pay for recursive programming.
// The code looks very easy, but internally the computer has to do lots of memory management,
// causing overhead that is consuming resources you'd better use for what you're up to, which is sorting.
// The createIndex method defined in the file hr$arraysort.js is a non-recursive variant of the
// last method described here.
//
// for seeing these algorithms in action you can start the script hr$arraysortdemo.wsf
// ====================================================================================================================
// End of file -- Copyright (c) 2003,2004  Henk Reints, http://henk-reints.nl