Re: Length-unaware sorting algorithm

[Sean Conner <sean@...>]

It was thus said that the Great Soni L. once stated:
> 
> If you wanna try this as a challenge: 
> http://codegolf.stackexchange.com/questions/91143/sort-an-array-without-knowing-its-length#
> 
> (And no, ipairs() and stuff is not allowed. ipairs() looks for the first 
> nil and treats that as the array boundary, which in this case counts as 
> an explicit length calculation.)

  You're moving the goal posts YET AGAIN!  I quote from your question on
Code Challenge:

	The end of the array is a sequence of some value we'll call
	$PLACEHOLDER repeated for the same length as the array itself. You
	can (and should) use this to your advantage.

  In the case of Lua, $PLACEHOLDER is nil.  

  So, can we use nil, or not?  What is the difference between ipairs()
stopping on a nil, and our code stopping on a nil?  Just how are we to
detemine the end of input?

  Soni, if you are *really* interested in the answer, I implore you to read
Chapter 5 of _The Art of Computer Programming_ by Donald Knuth.  It's a
quick read [1] that covers everything there pretty much is to know about
sorting and then some.  You should be able to find a copy via a library
(it's a bit pricy).  

  -spc (More specifically, Chapter 5, section 2, "Internal Sorting".  That's
	an even quicker read at about 100 pages)

[1]	Only 388 pages. And yes, that's 388 pages for Chapter 5 alone.